geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC197E Traveler

解説を見て解きました。

 

問題文の条件は、同じ色を連続して全て取ってから次の色を取るということを示します。

入力例1なら、32123の順で並んでいるボールを12233の順で取ります。同じ数字内での取り方に指定はありません。

 

ある色iのボールを全て取ることを考えます。

iの中で、最も小さい座標をL_i、大きい座標をR_iとします。

 

どのような順番でボールを取ったとしても、必ずL_iR_i間の移動が発生します。

そのため、この移動の際に全てのボールを回収することにしても問題ありません。

 

このように考えると、ボールの取り方は以下の2パターンしかありません。

  1. L_iから開始して、最後にR_iのボールをとる
  2. 上の逆パターン

 

次の色のボールを取得するときは、最後にボールをとった地点からの移動のみを考えればよく、これはL_iR_iの2パターンの状態しかありません。

 

よって、以下のdpが考えられます。

dp[i][j]:=iにおいて、最後にjにいるときの最小値。

但し、j=\{0,1\}とし、0のときはL_i、1のときはR_iにいるとします。

 

遷移は、

  1. L_{i-1} \rightarrow R_i \rightarrow L_i
  2. R_{i-1} \rightarrow R_i \rightarrow L_i
  3. L_{i-1} \rightarrow L_i \rightarrow R_i
  4. R_{i-1} \rightarrow L_i \rightarrow R_i

の4パターンに基づいて行えばよいです。

 

実装上、

  • iに該当する色のボールがないときはi-1を引き継ぐ
  • 色0座標0のボールと、色N+1座標0のボールの2つがあるとみなす

としておきます。

 

提出コード:https://atcoder.jp/contests/abc197/submissions/25514695