Codeforces Round #696(Div. 2) D Cleaning - 文学徒が競プロをするブログ

典型が二つほどあって勉強になった。まあ解説見た後12WAしたんですけど......。

問題概要

数列が与えられる。隣合う二つの数が1以上の時、その二つの数を両方とも1減らすことが出来る(片方だけ減らすなどは出来ない)。
適切に操作を行ったとき、数列の要素を全て0に出来るか？ただし 一度だけ任意の隣接する二点をswapすることが出来るものとする。

という問題。

解法

一度に全てを考えようとするととっつきずらいので、まずswapなしの問題を考えてみる。例えば $A = \langle 10, 5, 8, 3 \rangle$ のような数列が与えられたとする。実はこれは絶対に全ての要素を0にすることが出来ない。何故なら $A_0 > A_1$ だからである。一番端の要素は二番目の要素としか数を減らせないため、必ず $\langle 5, 0, 8, 3 \rangle$ より良い状況にはならない。

逆に $A_0 \leq A_1$ の数列、例えば $A = \langle 5, 10, 8, 3 \rangle$ を考えてみる。
するとこれは左端から操作すると $A = \langle 0, 5, 8, 3 \rangle$ となるのだが、 $A_0$ は0になったために以降考慮の必要がなくなり、 $A_1$ を一番端の要素として扱えるようになる。
つまりこの数列は更にこうなって $A = \langle 0, 0, 3, 3 \rangle$
最後にこうなる $A = \langle 0, 0, 0, 0 \rangle$

というわけで、条件を「一番端の要素は二番目の要素よりも小さくなくてはならない」という話に一般化し、それを再帰的に(これ使い方微妙に違う気がするんだけどいい言葉が思いつかなかった)適用することで判定が出来る。
これ典型というか競技プログラミングっぽくて好き。

ではこの解法をswapありでも適用できるように拡張していく。
まあswapする位置を全部試さないことにはどうしようもなさそうな見た目をしているので、全部試す方針でいく。
ここでもう一つの典型だが、 隣接する二点をswapする → 二点の周囲以外は状況が変わらない ことを念頭に置く。

その上で「一番端から数字を減らしていく」ことを思い出そう。
すると左から減らしていった数値を保持しておく数列 $l$ と右から減らしていった数値を保持しておく数列 $r$ をそれぞれ持ち、隣接する二点の周囲だけもう一度計算し直してやれば良いという着想を得ることが出来る。

これを実装すれば解けるのだが、端から減らしていった数が一度でも数が負の数になったらダメということを忘れていて死ぬほどWAした。
学びのある問題だったが辛かった。