TopCoder SRM 516 Div1 Medium RowsOrdering

1WAしてしまったけど、解法はすんなりたどり着いた。
http://community.topcoder.com/stat?c=problem_statement&pm=11114

問題

a～z及びA～Xの計50種類の文字M個から生成された文字列がある。
このような文字列は当然50^M通りある。
これらの文字列を以下の順で並べ替える。

1. 各列において、a～Xの順列をそれぞれ定める。
2. M列のpermutationを定める
3. 上記2種の情報を用いて以下の手順で文字列をソートする：
   1. 2番目のpermutationの順で各列の文字を比較する
   2. 各列の大小比較は1番目の順列により定める

文字列集合R[i]に対し、ソート後の全文字列群(50^M)内の順位の総和を最小化せよ。

解法

この問題は以下のように書き換えられる。

「各文字列を50進数と見なす。各桁の順の入れ替えが可能であり、かつ各桁内での各文字の0～49への対応を変えられるとき、R[i]の総和を最小化せよ」

以下の2段階の手順で行う。

• 各桁内での文字と0～49の対応を決める
• 桁の順番を決める

求めるのは総和なので、前者は当然登場回数が多い順に0,1,2...と求めればよい。
そのように求めると各桁について、R[i]の総和が求まる。

次に後者の処理では、先に求めた各桁の総和を小さい順に上の桁に割り当てればよい。

ll mo=1000000007;

class RowsOrdering {
	public:
	int H,W;
	ll p50[51];
	int order(vector <string> rows) {
		H=rows.size();
		W=rows[0].size();
		int x,y,j,i;
		
		p50[0]=1;
		FOR(x,50) p50[x+1]=p50[x]*50%mo;
		ll ret=H;
		
		int num2[55];
		ZERO(num2);
		
		FOR(x,W) {
			int num[55];
			ZERO(num);
			FOR(y,H) {
				if(rows[y][x]>='a' && rows[y][x]<='z') num[rows[y][x]-'a']++;
				if(rows[y][x]>='A' && rows[y][x]<='Z') num[rows[y][x]-'A'+26]++;
			}
			sort(num,num+51);
			reverse(num,num+51);
			num2[x]=0;
			FOR(i,51) num2[x]+=i*num[i];
		}
		
		sort(num2,num2+W);
		reverse(num2,num2+W);
		FOR(x,W) ret=(ret+num2[x]*p50[x])%mo;
		
		return (int)ret;
	}
}

まとめ

このぐらいの問題だと自力で解けるな。