解説を見て解きました。
問題文の条件は、同じ色を連続して全て取ってから次の色を取るということを示します。
入力例1なら、32123の順で並んでいるボールを12233の順で取ります。同じ数字内での取り方に指定はありません。
ある色のボールを全て取ることを考えます。
色の中で、最も小さい座標を
、大きい座標を
とします。
どのような順番でボールを取ったとしても、必ず⇔
間の移動が発生します。
そのため、この移動の際に全てのボールを回収することにしても問題ありません。
このように考えると、ボールの取り方は以下の2パターンしかありません。
から開始して、最後に
のボールをとる
- 上の逆パターン
次の色のボールを取得するときは、最後にボールをとった地点からの移動のみを考えればよく、これはと
の2パターンの状態しかありません。
よって、以下のが考えられます。
色
において、最後に
にいるときの最小値。
但し、とし、0のときは
、1のときは
にいるとします。
遷移は、
の4パターンに基づいて行えばよいです。
実装上、
- iに該当する色のボールがないときはi-1を引き継ぐ
- 色0座標0のボールと、色N+1座標0のボールの2つがあるとみなす
としておきます。
提出コード:https://atcoder.jp/contests/abc197/submissions/25514695