SRM620 Div1 Medium "CandidatesSelection"
問題
TopCoder Statistics - Problem Statement
訳
キツネのシエルは新しくメイドを雇うことにした。n人の候補者が並んでおり、料理や洗濯の上手さ、慎重さといった、m種類のスキルをパラメータとして持っている。シエルは候補者に0～n-1、スキルに0～m-1と番号を付けていた。
シエルは各候補者の各スキルについて評価をした。この情報をm文字で構成されたn個の文字列String scoreとして、あなたに与えられる。score[i][j]はi番目のメイドのj番目のスキルの評価値を表している。その文字はAからZのアルファベットであり、Aが最高でZが最低であることを示す。
今現在、候補者達は{0, 1, ..., n-1}と並んでいる。シエルはメイドの雇用について、数日間考えた。各一日で、彼女は１つのスキルを選択し、そのスキルを最も良く出来る者から最も出来ない者という順で、候補者を並び替えた。ただし、複数の候補者が選択したスキルにおいて同じレベルであったときは、前日までの順序を保つことにした。
あなたは0～n-1の順列であるint resultが与えられる。０日以上シエルが候補者の並び替えを行ったときに、resultのように並び替えることができるかどうかを返せ。
制約
1 <= n, m <= 50
考えたこと
TopCoder SRM 620 Div1 Medium CandidatesSelection - kmjp's blogを参考にさせて頂きました。m(_ _)m
start({0, 1, ..., n-1)からresultへ考えるのではなく、逆にresultからstartへ戻せるか考えます。
戻すにあたって、0～m-1のソート方法を適用していくのですが、いやこのソート方法は使えないよね、というのがでてくる。
サンプル５を使って説明すると、まずresultは
{3,7,1,0,2,5,6,4}
で、ソート方法は
0 : [3, 7] < [1] < [0, 2, 4, 5, 6] 1 : [1] < [0, 6] < [2, 3, 4, 5, 7] 2 : [3, 5] < [0, 7] < [1, 2, 4, 6] 3 : [5] < [0, 1, 3, 4, 7] < [2, 6] 4 : [1, 2, 6] < [0, 3, 4, 5] < [7] 5 : [0, 2, 3, 7] < [1] < [4, 5, 6]
な訳です。
ここで、resultにしたときに、どのソートを使ったんだろうと考えると、ソート１とかはダメです。なぜならresultでは1は7より右にありますが、ソート１では1は7より左にきてしまうから。
ソート０はそこのところ優秀。なのでソート０を使ってresultを作ったのかな～と推測してやると、
{3,7,1,0,2,5,6,4}
↓ソート０
{3,7},{1},{0,2,5,6,4}
となる。ここでカッコは何を意味するかというと、左右関係を気にするグループを意味します。つまり、3と0などはソート０を使うと正しく左右に振ってくれることが確定するので、これ以前のソートでは左右関係を気にしなくてもよいのです。
{..., 0, ..., 3, ...}
↓ソート０
{..., 3, ..., 0, ...}
その代わり、0と5など同じグループにいるもの同士はこれ以前のソートで左右関係を守らなくてはならないことを意味します。
{..., 5, ..., 0, ...}
↓ソート０
{........, 5, 0, ...}←はいダメ
また、グループが全て昇順になっていないため、ソート０を使っただけではresultにならないことも分かります。
{0,1,2,3,4,5,6,7}
↓ソート０
{3,7},{1},{0,2,4,5,6}←ソート０を使用してOKならこうなっているはず
次にソート５が優秀なようですので、ソート５を適用します。
{3,7},{1},{0,2,5,6,4}
↓ソート５
{3,7},{1},{0,2},{5,6,4}
この時、{0,2,5,6,4}グループは{0,2},{5,6,4}の２つのグループに分かれます。なぜかというと、ソート５を適用したときに{0,2}が{5,6,4}の左に来ることが確定するからです。
まだ昇順でないグループ{5, 6, 4}が残っているので、どんどん進めます
{3,7},{1},{0,2},{5,6,4}
↓ソート２
{3},{7},{1},{0},{2},{5},{6,4}
↓ソート１
{3},{7},{1},{0},{2},{5},{6},{4}
ここまでくると、全部ばらばらのグループになってしまったので、昇順となっていることは明白です。よって、Possibleであるといえます。
逆に、グループが昇順になっていない状態でどのソートも適用できなくなってしまったら、Impossibleであるといえます。
この解法を使ったとき、以下のことが言えます。
・同じソート方法を使用する意味はない。
・ある場面で複数のソート方法を適用できた場合、どれを先に使ってもよい
よって、グループを分割する処理は最大m回で済むことになります。
事後
うーん・・こんなの思いつかねぇ・・
ソースコード
class CandidatesSelection { public: int N, M; vector<string> S; bool mused[55]; string possible(vector <string> score, vector <int> result) { N = result.size(); M = score[0].size(); S = score; // 始めはresult順で全て同じグループ vector<vector<int>> v; vector<int> e(result); v.push_back(e); memset(mused, false, sizeof(mused)); return dfs(v) ? "Possible" : "Impossible"; } bool dfs(const vector<vector<int>> &v) { // 昇順チェック bool end = true; for (int i = 0; i < v.size(); i++) { for (int j = 1; j < v[i].size(); j++) { if (v[i][j - 1] > v[i][j]) end = false; } } // 全て昇順になっていればtrueを返す if (end) return true; // ソートの仕方を一通り for (int m = 0; m < M; m++) { if (mused[m]) continue; bool ok = true; // 各グループを一通り for (int i = 0; i < v.size(); i++) { for (int e1 = 0; e1 < v[i].size(); e1++) { for (int e2 = e1 + 1; e2 < v[i].size(); e2++) { // 矛盾があれば、このソートは使えない if (S[v[i][e1]][m] > S[v[i][e2]][m]) ok = false; } } } if (!ok) continue; mused[m] = true; // 使えるならグループ分割 vector<vector<int>> nvv; bool used[55]; memset(used, false, sizeof(used)); for (int i = 0; i < v.size(); i++) { for (int j = 0; j < v[i].size(); j++) { int p1 = v[i][j]; if (used[p1]) continue; vector<int> nv; nv.push_back(p1); used[p1] = true; for (int k = j + 1; k < v[i].size(); k++){ int p2 = v[i][k]; if (used[p2]) continue; if (S[p1][m] == S[p2][m]) { nv.push_back(p2); used[p2] = true; } } nvv.push_back(nv); } } return dfs(nvv); } // 一通りやってだめならfalseを返す return false; } };
