ABC346、D問題の解説

0. はじめに

前処理による解法です。やってることは公式解説と同じですが、公式解説より理解が容易だと思います。

1. 問題とACコード

2. 解法概要

1. 与えられた文字列Sを、0と1が交互に出現する文字列と1と0が交互に出現する文字列、文字列「0101...」と「1010...」に変更することを考え、そのための累積コストを計算します。
2. 「0101...」と「1010...」の文字列を各位置でつなぎかえると、問題文で求められている良い文字列ができます。（例、5文字の文字列の4文字目以降をつなぎかえる）
   • 01001
   • 10110
3. 文字列「0101...」と「1010...」を作成するための累積コストを前処理として計算しているので、良い文字列を作成するための累積コストの和を$O(1)$で計算できます。
4. つなぎかえる位置を全探索して、良い文字列作成のための最小コストを得ることができます。

3. 終わりに

• 問題文を読んだときに、「00」と「11」の位置を全探索するのだろうとは思いました。
• ただ、その前後の文字列作成のコストのうまい処理方法を思いつかなかったので、まず文字列「0101...」と「1010...」を作成するための累積コストを計算しました。
• そこで文字列「0101...」と「1010...」を見て、これらの文字列を途中でつなぎかえれば良い文字列を作成できるとわかりました。
• 全ての良い文字列の作成コストを$O(1)$で計算できるので、最小コストを全探索から求めることができました。