ABC 401-500/ABC454F - Make it Palindrome 2 - 競技プログラミング用 知識集積所

---

問題

ABC454F

必要知識

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

• 考察問題
• 貪欲法（アルゴリズム系）※

考え方

考察問題。
問題を言い換えていく。

まず、中央をまたぐ操作というのは、できないことにしてよい。
例えば長さが9のとき、4から8までに1を加えるのは、7から8までに1を加える操作で代用できる。
なぜなら、中央の5に1を加えるのは回文の成否に無関係だし、4と6の両方に1を加えるのも同様。
あるいは、長さが8のとき、1から5までに1を加えるのは、1から3までに1を加える操作で代用できる。
長さが8のとき、3から6までに1を加えるのは、そもそもやる意味がない。
ということで、以下は「中央をまたがない範囲のみ操作が認められる」と考える。

そして、「前半のある区間全てに1を足す」という操作は、「後半の対称区間全てから1を引く」と考えてよい。
これもやはり、回文の成否について考えるならどちらでも同じことだからである。
これで、「後半のある区間全てに1を足すか1を引く」の回数を考える問題になった。

さらに、「後半のある区間全てに1を足すか1を引く」は、「後半のある箇所以降全て+1し、同時にある箇所以降全て-1する」と変えることができる。
（終端を選ぶことで、片方だけやってもよいものとする）

ということで、「後半のある箇所以降全て+1する」と「後半のある箇所以降全て-1する」を好きなだけ繰り返して回文を作り、多かった方の操作回数最小値を目指す問題となった。

さて、「ある箇所」ごとに、どちらの操作を何回やればよいかは、2択に決まる。
というのは、前半が全く動かせない以上、後半を正確に指定数列にするしかなく、+1を使うか-1を使うかの自由度しかないためである。

最後に、ではどこを+にしてどこを-にするとよいのかを考える。
ある箇所Aでは、+ならi回、-ならm-i回必要とする。
ある箇所Bでは、+ならj回、-ならm-j回必要とする。
i<jだとする場合、Aを-側、Bを+側にすることは絶対にない。
なぜなら、Aを+側、Bを-側にすれば、両方の操作の回数を減らせるのだから。
ということは、+の回数が少ない側から優先して+で採用、-の回数が少ない方から優先して-で採用してあるパターンのみ考える貪欲法※が成立する。
deque※上で+の回数をソートしておき、先頭の値を+回数に足すか、m-末尾の値を-回数に足すか、足した後の値が小さくなる方をdeque※がなくなるまで実行していけばいい。

解答例

解答例

注意点

long long型を用いる

ほぼすべての箇所を半周回すような入力だと、途中の累積値や答えがint型をはみ出ることがある。

別解