天下一プログラマーコンテスト2015 予選B : D - 天下一電卓英作文

このテク昔使ったことあるはずなのに思い出せなかった…。
http://tenka1-2015-qualb.contest.atcoder.jp/tasks/tenka1_2015_qualB_d

問題

電卓等で使われる7セグメントフォントは、180度回転するとアルファベットに見える。
0→OまたはD
1→I
2→Z
3→E
4→h
5→s
6→q
7→L
8→B
9→G

ここでいくつか上記文字のみで構成された単語が与えられる。
D桁まで表示できる電卓で表示できる最大の数値のうち、180度全体をひっくり返すと与えられた単語の連結となるようなものを答えよ。
なお、leading zero表記したい場合は小数でなければならない。
また、同じ単語を複数回利用してはならない。

解法

与えられた単語をまず反転させ、数字の列に直そう。
あとはこれを連結して得られるD桁以内の最大値を求めればよい。

まず、各単語を順に並べるわけだが、その際最終的な数値が大きくなるようなものを上の桁に置くのが良いのは明らかである。
ではどの順に置けばそうなるか。

2つの単語A,Bがあったとき、A+B＜B+Aならば、Aを先に置いた方が全体が小さくなる。
…という比較関数を用いて単語群を降順ソートすると、先に置いたら全体が大きくなる順に単語群を並べることができる。
あとは単語群を使って得られる単語の連結のうち最大の(D以下の)桁数のものをDPで求めればよい。

int D,N;
string S[10100];
string mp="DIZEhsqLBGO";
string s[240];

void solve() {
	int i,j,k,l,r,x,y;;
	
	cin>>D>>N;
	
	int allzero=1;
	FOR(i,N) {
		cin>>S[i];
		FORR(r,S[i]) FOR(x,11) if(r==mp[x]) r='0'+x%10;
		reverse(ALL(S[i]));
		if(S[i][0]!='0') allzero=0;
	}
	
	sort(S, S+N, [](string &a, string &b){return a + b < b + a;});
	
	FOR(i,N) {
		string t=S[N-1-i];
		int l=t.size();
		for(j=200;j>=0;j--) if(j==0 || s[j].size()) {
			if(j+l>D) continue;
			if(!allzero && j==0 && t[0]=='0') continue;
			s[j+l]=max(s[j+l],s[j]+t);
		}
	}
	if(allzero) {
		string ma;
		FOR(i,D+1) {
			while(s[i].size() && s[i].back()=='0') s[i].pop_back();
			ma=max(ma,s[i]);
		}
		if(ma.size()) cout<<"0."<<ma.substr(1)<<endl;
		else cout<<0<<endl;
	}
	else {
		for(i=D;i>=0;i--) if(s[i].size()) {
			cout<<s[i]<<endl;
			break;
		}
	}
}

まとめ

A+BとB+Aの比較で並べ替えるテク、だいぶ前に使ったので思い出せなかったな…。