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; } };