Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 251 E問題 Tahakashi and Animals

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

集合  E があり, 最初,  E=\emptyset である.

次の操作を好きなだけ行なう.

  •  A_1 円払い,  E 1,2 を加える.
  •  A_2 円払い,  E 2,3 を加える.
  •  A_3 円払い,  E 3,4 を加える.
  •  \vdots
  •  A_i 円払い,  E i, (i+1) を加える.
  •  \vdots
  •  A_{N-1} 円払い,  E (N-1), N を加える.
  •  A_N 円払い,  E N, 1 を加える.

 E=\{1,2, \dots, N\} にするためには最低何円必要か?

制約

  •  1 \leq N \leq 3 \times 10^5
  •  1 \leq A_i \leq 10^9

解法1

 A_i 円払い,  E i, (i+1) を加える.」という操作を操作  i ということにする.

このとき,

  •  i \in E にするためには, 操作  (i-1) と操作  i のうちのどちらか一方を行わければならない (操作  0 は操作  N とする).

ということになる. ここで,  i \geq 2 のときは  i-1,i とつながっているが,  i=1 のときは  N,1 であるというこから, ここに着目する. より詳しく, 操作  N をするかどうかで場合分けする.

解法2

操作  N をしない場合, 次の動的計画法  {\rm DP}[i,x] を考える.

  •  {\rm DP}[i,x=] 操作  i まで見た時, 要求を満たし, しかも操作  i x=F ならばしない,  x=T ならばする操作達の費用の最小値

このとき, ベースケースは操作  N をしないということに着目すると,

 {\rm DP}[1,x]=\begin{cases} \infty & (x=F) \\ A_1 & (x=T) \end{cases}

である. 遷移式は操作  i-1, i を続けてしないということはできないということに着目すると,

 {\rm DP}[i,F]={\rm DP}[i-1,T], \quad {\rm DP}[i,T]=\min ({\rm DP}[i-1, F], {\rm DP}[i+1, T])+A_i

である. この場合の答えは, 操作  N-1 は必ずしないといけないので,  {\rm DP}[N-1, T] である.

解法3

操作  N をする場合は上と同様にして求めることができるが, 次の部分が異なる (動的計画法 {\rm DP}'[i,x] とする).

  • ベースケースは  {\rm DP}'[1,F]=A_N, {\rm DP}'[1,T]=A_1+A_N である.
  • 遷移式は上と同様である.
  • 最終解答は操作  N-1 はやってもやらなくてもいいので,  \min ({\rm DP}'[i,F], {\rm DP}'[i,T]) である.

解法4

以上から, 操作  N をするかしないかで場合分けし, 各場合における最小費用を求めたので, この2つのうちの小さい方が最終解答になる.