問題の勘違いはな。
問題
TopCoder Statistics - Problem Statement
以下の条件を満たす文字列を求めよ。ただし, 解が複数ある場合は辞書順最小のものを求めよ。
- 文字列の長さは N
- 文字列は 'a', 'b' のみで構成される
- 配列 x が与えられる。長さ i+1 の部分文字列で,「 同じ文字が i+1 回連続で続く」というもの(constant と呼ぶ)がちょうど x[i] 個ある。
解法
配列 x のインデックスが大きいものから考えると, 「長さ i+1 の constant があれば 長さ j+1 の constant は i-j+1 個ある(j <= i)」 が成り立つので, それぞれの長さの constant の個数を一意に定めることができます。
後は辞書順最小にするパートです。明らかに答えは 'a' の constant と 'b' の constant が交互に並んだような形になります。これはなるべく前半に多く 'a' を入れて なるべく少ない 'b' を入れておくのが良いです。
class BearPasswordLexic { public: string findPassword(vector <int> x) { int N = x.size(); if (x[0] != N) return ""; vector<int> cnt; for (int i = N-1; i >= 0; i--) { if (x[i]) { for (int j = 0; j < x[i]; j++) { cnt.push_back(i+1); } for (int j = 0; j <= i; j++) { x[j] -= (i-j+1) * x[i]; if (x[j] < 0) return ""; } } } int l = 0, r = cnt.size()-1; int now = 0; string ans; while (l <= r) { if (!now) { for (int i = 0; i < cnt[l]; i++) { ans += 'a'; } l++; } else { for (int i = 0; i < cnt[r]; i++) { ans += 'b'; } r--; } now ^= 1; } return ans; } };
あ, "return the lexicographically smallest of them" だったのか(勝手に "return the any of them" にしてた)
— マヨ子@大天使クサハエル (@mayoko_) 2016年7月19日
仕方ないね(白目)