JOI2019 本選 C - たのしいたのしいたのしい家庭菜園

• 問題
• AC

左から列を作っていくとして、次にR, G, Yを隣に置くためにはまだ使っていないものの中で一番近いものを持ってくればよい。今までにR, G, Yをそれぞれ何個使ったか保持していれば一番近いR, G, Yがどこにあるかは決まるので、$\operatorname{dp}[x][y][z][c] :=$Rを$x$個、Gを$y$個、Yを$z$個使っていて直前に置いた色が$c$である場合の最小コスト、というDPが${O}(N^3)$でできるはず……だが、それ以降のほうが難しかった。

例えば$\operatorname{dp}[x][y][z][c]$から次にGを隣に持ってきて$\operatorname{dp}[x][y+1][z][G]$に遷移するとき、何回スワップが必要か数える必要があるのだが、どうやって数えるかでしばらく悩んでいた。結論から言えば

1. $\max(0, 次のGの位置以前にあるRの総数 - x)$
2. $\max(0, 次のGの位置以前にあるYの総数-z)$

の和が間にあるG, Yの総数に等しく、これが必要なスワップの総数に等しい。