AGC032 A 考察

AGC032 A - Limited Insertion

解説 AC 。……なんだけど解説を見てもよく分からなかった。おおまかに言うと完成形である b から逆順にたどって構築できるかを確認する。

b を操作によって構築可能な文字列と仮定する。そのとき i 番目が i になっている箇所が必ずある。その箇所を順に取り除いていく。複数箇所ある場合はもっとも右側の箇所を優先的に取り除く。左側を取り除いてしまうと位置が左にずれてしまい取り除けなくなることがあるからだ。これを繰り返して最後まで取り除けるなら構築可能である。取り除いた数字を記録しておき出力すれば答えになる。もし最後まで取り除けないなら構築不可能な文字列なので -1 を出力する。これは O(N^2) で N <= 100 なので間に合う。

https://atcoder.jp/contests/agc032/submissions/15859883

熱は下がったがのどが痛い。