SRM695 Div1 Easy "BearPasswordLexic"
解法
最終的に使用するconstantの長さとその数について、実は一意に定まる。
以下を見て欲しい。
constantの長さ | 1 2 3 4 数 | 11 8 5 2 ↓ constants 4 を1回使うと残るのは ↓ constantの長さ | 1 2 3 4 数 | 7 5 3 1 ↓ constants 4 をもう1回使うと残るのは ↓ constantの長さ | 1 2 3 4 数 | 3 2 1 0 ↓ constants 3 を1回使うと残るのは ↓ constantの長さ | 1 2 3 4 数 | 0 0 0 0 ってことは、 constant 4 を 2回 constant 3 を 1回 使うんだね!☆(ゝω・)vキャピ
で、辞書順に最小にしなければならないので、まず a を使うべきであろう。
そして、aを使う時はconstantの長さが長いほど良いので、最大のものを使うようにする。
次は b を使わなければならない。
そして、bを使う時はconstantの長さが短いほど良いので、最小のものを使うようにする。
constant 4 を 2回 constant 3 を 1回
だと、答えは"aaaabbbaaaa"となる。
ソースコード
class BearPasswordLexic { public: string findPassword(vector<int> x) { int n = x.size(); // ここで、x[0]=nでなければ失敗 if (x[0] != n) return ""; // 使用するconstantとその数を計算する int constants[55]; memset(constants, 0, sizeof(constants)); for (int k = 0; k < n; k++) { for (int i = n - 1; i >= 0; i--) { if (x[i] != 0) { constants[i]++; for (int j = i; j >= 0; j--) { x[j] -= i - j + 1; } break; } } } // ここで、全て0になっていなければ失敗 for (int i = 0; i < n; i++) { if (x[i] != 0) return ""; } // aからスタート string answer = ""; bool curA = true; while (true) { if (curA) { // aだったら一番大きいconstantを使用する int id = -1; for (int i = n - 1; i >= 0; i--) { if (constants[i] != 0) { id = i; constants[i]--; break; } } if (id == -1) return answer; for (int i = 0; i <= id; i++) { answer += "a"; } } else { // bだったら一番小さいconstantを使用する int id = -1; for (int i = 0; i < n; i++) { if (constants[i] != 0) { id = i; constants[i]--; break; } } if (id == -1) return answer; for (int i = 0; i <= id; i++) { answer += "b"; } } // ab入れ替え curA = !curA; } } };