TopCoder SRM 516 Div1 Medium RowsOrdering

問題

n行m列の行列が与えられる。
それぞれの成分の値は0以上50未満の整数であり、全ての行は異なっていて、
なおかつ可能な全ての行が含まれている。


この行列の行を以下のような手順でソートする。

  • それぞれの列ごとに、1〜50の順列を作成する。この順列は異なる列で同じものであってもよい。
  • 1〜Mの順列を作成する。
  • それぞれの行を以下のように比較して、ソートする
    • 手順2で作成した順列が小さい列から見る。
    • もし二つの行のその列の値が同じなら順列の次の列を見る。
    • 違うなら、手順1で作った、その列の順列で最初に出てくるほうが小さい。


こうして全ての行を並べ終えた後、
rows[]のそれぞれの要素が1-indexedで何行目にあるかをp[i]とする。
p[i]の最小値を求め、それをmod 10^9 + 7で答えよ。

制約条件

rowsの各要素は等しい長さを持つ。
rowsの要素の数≦50

方針

それぞれの列ごとに、
出現頻度の多い文字に、低い順列を割り当てる。
そしたら、その列の順列の合計の値を求める。


合計の値の小さい順に、比較に最初に使う列とする。
50進法の値と見れば、pの合計値が求まる。
1-indexedなのでnを足したのが答え。

ソースコード

class RowsOrdering {
  public:
  int order(vector <string> rows) {
		int n = rows.size(), m = rows[0].size();
		vector<vi> vec(n, vi(m));
		
		vi sums;
		rep(i, m){
			int cnt[256] = {};
			rep(j, n) cnt[(int)rows[j][i]]++;
			vector<pi> v;
			rep(j, 256) v.pb(mp(cnt[j], j));
			sort(all(v), greater<pi>());
			
			int sum = 0;
			rep(j, n) rep(k, 256) if(rows[j][i] == v[k].second){
				sum += k;
				break;
			}
			sums.pb(sum);
		}
		sort(all(sums));
		ll ans = 0;
		rep(i, m) ans *= 50, ans += sums[i], ans %= mod;
		
		return ans + n;
  }
};