ABC 401-500/ABC459D - Adjacent Distinct String - 競技プログラミング用 知識集積所

---

問題

ABC459D

必要知識

B以下レベルの内容は省略

• 貪欲法（アルゴリズム系）※

考え方

構成できる場合、「直前文字と異なる文字のうち、並べなきゃいけない残り個数が最大であるものを次に置く」という貪欲法※が成立する。

証明は以下。
仮に、直前の文字がa、並べなきゃいけない残り個数が最大であるものがbだったとする。
この状況で、仮に次にcを置く解が存在したとする。
この場合、その解のこの位置のcをbに変更し、次がbだった場合にはそれをcに、その次がcだったらそれをbに、と変更する。
bをcに変えたところで連鎖が途切れるなら、bとcの個数が変わらないまま、次にbが来る解に変更できた。
cをbに変えたところで連鎖が途切れるなら、bは1つ増えて、cは1つ減ってしまっている。
しかし、bの個数はcの個数以上あるので、他の部分で(c以外)bcbc……cb(c以外)となっている部分が必ず1つ以上あるため、そこのbとcを全て入れ替えればよい。
こうして、直前の文字がa、並べなきゃいけない残り個数が最大であるものがbだった場合、ここから先の解が存在するなら、その中に次にbを置くものが含まれていることが示された。
これは直前の文字が他の文字であったり、並べなきゃいけない残り個数が最大であるものが他の文字であったりする場合にも成り立つ。

ということで、この貪欲法※で文字列を作っていけばよい。
高々26種類しか文字がないので、長さ26の個数カウンタを毎回調査してもいいし、priority_queue※などを用いてもよい。

この方法で作成失敗する場合はNoである。
実際に作ってみて失敗検出するコードを書いてもいいし、そもそも手順を考えれば、全体の長さの半分（切り上げ）+1個以上同じ文字があれば不可能という判定をしてもよい。

解答例

解答例

注意点

別解