ARC 201-300/ARC207E - Erase and Append - 競技プログラミング用 知識集積所

---

問題

ARC207E

必要知識

簡単な内容は省略

• 考察問題

考え方

考察問題。

いろいろ試してみると、0ABC...XYZ1またはという形の部分について、間のABC...XYZの部分を削除しながら、後ろに同じ文字数の好きな文字列を作ることができるとわかる。
すなわち、

• 0を用意したいタイミングでは、先頭の0をコピーし、その右隣を消す
• 1を用意したいタイミングでは、末尾の1をコピーし、その左側を消す

というのを文字数分繰り返せばよい。
これは、1ABC...XYZ0という形でも0と1の立場を入れ替えれば同様である。

ということは、

• sの中に0も1もあるなら、まず最初に先頭と末尾で異なる文字にする（1手で確実に可能）
  • 先頭の文字と異なる文字が最初に出てくるところを探し、それをコピー+その左右どちらか（先頭ではない方）を消す
• sの両端以外を削除し、sの末尾にtの両端以外のn-2文字を作る（n-2手で確実にできる）
• 最初の文字を揃える、つまり、sの先頭2文字のうち、tの先頭と異なる方を消す（1手）
• 末尾の文字がsとtで異なるなら、頑張ってその文字を揃える
  • 末尾の文字と異なる文字が最後に出てくるところを探し、それをコピー+その右を消す

で合計n-1手で一部の特殊ケース以外はうまくいく。

文字列によってうまくいかない可能性があるのは、

• 2文字の文字列だと1段階目で話がややこしくなる
  • 先頭の文字を残す方法が、先頭をコピー元に選ぶ以外ないため
• sが全部0か1だと、1段階目が失敗する。この場合、そもそも一致していた場合以外は不可能。
  • sにない文字を無から作れないため。
• tが最後の1文字以外全部同じ文字で、最後1文字だけ異なる場合は、そもそも一致していた場合以外は不可能。
  • 最後1回の操作をする前がどんな文字列だとしても矛盾するため

あたり。
よって、これらを適切に除外しながら前述の方法を実装すればよい。
もともとsとtが一致していたら0と出力、を最初に書くと楽。

解答例

解答例

注意点

別解