みんなのプロコン2019 D-Ears をPython で解いてみる

問題文が迷わせに来ていますね.

全ての要素は非負ですので, りんごさんの要望を $\left\{A_i\right\}_{i=1}^L$ , すぬけさんの石の置き方を $\left\{B_i\right\}_{i=1}^L$ としたときのコスト
\begin{equation}
\sum_{i=1}^L |A_i-B_i|
\end{equation}
を最小化すればいいことがわかります.

すぬけさんの動き方はりんごさんが好きに決められるので,

$\left\{A_i\right\}_{i=1}^L$ が与えられたとき, $\left\{B_i\right\}_{i=1}^L$ を最適に選んだときの最小コスト

を求めればよいことが分かります.

つまり,

りんごさんの要望 $\left\{A_i\right\}_{i=1}^L$ が先に与えられていて, すぬけさんの石の置き方を $\left\{B_i\right\}_{i=1}^L$ はそれに応じてよいものを選べる.

という問題設定です.

ただし, $\left\{B_i\right\}_{i=1}^L$ に対する制約は結構複雑です.
すぬけさんの移動に関しては, 順番を巻き戻しても石の配置は変わらないので出発点の座標 $S$ , 終了点の座標 $T$ の間には
\begin{equation}
S\le T
\end{equation}
なる関係があるとして一般性を失いません.

そして, 出発点と終了点の間の座標に置かれている石はかならず奇数個になっています.
すぬけさんは同じ座標を行ったり来たりすることで, 任意の奇数を実現できることに注意しましょう.
これにより, $A_i$ が奇数ならば $0$ までコストを下げられ, 偶数ならば $1$ までコストを下げられます.

また, すぬけさんは出発点よりも左に進むことができます.
すぬけさんが訪れる左端の座標を $D$ とすると, $D\le S$ であり, その区間に置かれている石はかならず $0$ ではない偶数個になっています.
これにより, $A_i$ が奇数ならば $0$ までコストを下げられ, $0$ でない偶数ならば $1$ までコストを下げられます.
$0$ であれば, この区間の最小コストは $2$ となります.

$D >0$ のときは, $D$ よりも左にはすぬけさんは移動していないことになるため, その区間に置かれている石は $0$ 個です.
これにより, 区間 $i$ におけるコストは $A_i$ そのものになります.

今までの議論は終了点の右に対しても行えます.
すぬけさんが到達できる右端の座標を $U$ とすると, これまでの議論は,

$D \le S \le T \le U$ は自由に取ることができる.
$i = 0,\cdots, D$ ならばその区間のコストは $A_i$ .
$i = D+1,\cdots , S$ ならばその区間のコストは $A_i \mod 2$ .
$i = S+1,\cdots , T$ ならばその区間のコストは $(A_i+1) \mod 2$ .
$i = T+1,\cdots , U$ ならばその区間のコストは $A_i \mod 2$ .
$i = U+1,\cdots , N$ ならばその区間のコストは $A_i$ .

という風にまとめられます.
それぞれの区間の長さは $0$ であってもよいものとします.

貪欲法が上手く働かない理由

例えば $L = 5$ として,
\begin{equation}
A = [1, 0,0,0,1]
\end{equation}
であれば右端は見捨てた $B =[1,0,0,0,0$ ] が最適（の１つ）であるのに対して,
\begin{equation}
A = [100,0,0,0,100]
\end{equation}
のような状況であれば $B = [100,1,1,1,100$ ] とするのが最適になり,
そういったものをどう処理するかを指定するのが難しくなります.

さて, 計算量を減らそう.

$D \le S \le T \le U$ を決定させればそのときの最小コストが求められることが分かりました.
しかしながら, それらをループで処理すると計算量は $O(L^4)$ となり計算が間に合いません.

ですので, 入力の長さ $L$ に対する動的計画法（ＤＰ）を考えます.
すなわち, $\ell = 0,1,\cdots, L$ を任意に取るごとに, $\left\{A_i\right\}_{i=1}^\ell$ が入力であったときの最小コストを求めましょう.

しかしながら, 安直なＤＰは働きません.

というのも, $\left\{A_i\right\}_{i=1}^\ell$ に対する状態の分割が $\ell+1$ では通用しないためです.
これを確かめるために, 先ほど挙げた $A = [100,0,0,0,100$ ] の場合を考えましょう.
今考案したＤＰにおいて, 入力が $\ell =4$ のときまでを考えると, $D=S=T=0, U=1$ が最適な配置であるのに対して,
$\ell = 5$ のときは, $D=0,S=1, T=4, U=5$ が最良となってしまいます.

というわけで, 入力の長さ $\ell$ だけでなく, 現時点での右端の"戦略"を $5$ 通り保持する必要があります.
ただし, $\ell$ をインクリメントする際には, 右端の"戦略" よりも新しいものだけが選べることに注意します.
具体的には,

コストが $A_i$ となる $i = 0,\cdots, D$ なる区間を状態 $0$ .
コストが $A_i \mod 2$ .となる $i = D+1,\cdots, S$ なる区間を状態 $1$ .
コストが $(A_i+1) \mod 2$ となる $i = S+1,\cdots, T$ なる区間を状態 $2$ .
コストが $A_i \mod 2$ .となる $i = T+1,\cdots, U$ なる区間を状態 $3$ .
コストが $A_i$ となる $i = U+1,\cdots, N$ なる区間を状態 $4$ .

と呼ぶことにすると, 例えば状態 $0$ で考えた場合には楽で,

先頭 $\ell +1$ までの文字列のなかで, 右端の状態が $0$ のときの最小コスト
＝先頭 $\ell$ までの文字列のなかで, 右端の状態が $0$ のときの最小コスト
　　+ $\ell+1$ 文字目を状態 $0$ で実行したときのコスト

となります. さらに状態 $1$ を考える場合には,

先頭 $\ell +1$ までの文字列のなかで, 右端の状態が $1$ のときの最小コスト
＝先頭 $\ell$ までの文字列のなかで, 右端の状態が $0,1$ のときの最小コスト
　 + $\ell+1$ 文字目を状態 $1$ で実行したときのコスト

となり, $\ell$ での状態を複数個使う必要があります.
以上のことをまとめると, 一般に, 次のような漸化式が成り立ちます.
\begin{align}
\textrm{DP}[\ell + 1][j]
&= \min_{k = 0,\cdots, j } \textrm{DP}[\ell + 1][k] + \textrm{cost}(j , A_\ell) ,\\
\textrm{cost}(j , A_\ell)
&= \begin{cases}
A_\ell &\quad \textrm{if } j =0,4,\\
A_\ell \mod 2 &\quad \textrm{if } j =1,3,\\
(A_\ell +1) \mod 2 &\quad \textrm{if } j =2
\end{cases}
\end{align}
あとはこれを実装します.

L = int(input())
A = [int(input()) for i in range(L)]

DP = [[0 for i in range(5)] for j in range(L+1)]

def cost(s, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(L):
    DP[i+1][0] = min(DP[i][:1]) + cost(0, A[i])
    DP[i+1][1] = min(DP[i][:2]) + cost(1, A[i])
    DP[i+1][2] = min(DP[i][:3]) + cost(2, A[i])
    DP[i+1][3] = min(DP[i][:4]) + cost(3, A[i])
    DP[i+1][4] = min(DP[i][:5]) + cost(4, A[i])

print(min(DP[L]))

これでめでたくＡＣしますね
https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4228991

が与えられたとき, を最適に選んだときの最小コスト

りんごさんの要望 が先に与えられていて, すぬけさんの石の置き方を はそれに応じてよいものを選べる.

貪欲法が上手く働かない理由

さて, 計算量を減らそう.

しかしながら, 安直なＤＰは働きません.

$\left\{A_i\right\}_{i=1}^L$ が与えられたとき, $\left\{B_i\right\}_{i=1}^L$ を最適に選んだときの最小コスト

りんごさんの要望 $\left\{A_i\right\}_{i=1}^L$ が先に与えられていて, すぬけさんの石の置き方を $\left\{B_i\right\}_{i=1}^L$ はそれに応じてよいものを選べる.