geam1113’s diary

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

AtCoder Beginner Contest 251 参加記録

ABC 少ない状態数構成問題

コンテスト中AC:A〜C,E

E - Takahashi and Animals

E - Takahashi and Animals

グラフの問題として考えていたので、言い換えておきます。

頂点 $0,...,N-1$ について、頂点 $i$ と頂点 $(i+1)\ mod\ N$ の間には辺 $i$ があり、そのコストは $A_i$ です。
ここから、以下の条件を満たすように辺をいくつか削除します。

すべての頂点の次数が1以上

残った辺のコストの総和をスコアとする時、スコアの最小値を求めてください。

辺がある時とない時で状態が2通りしかないので、 $i$ の小さい方から順にdpができないか考えます。

$dp[i][j]:=$ 辺 $i$ の状態が $j$ の時のスコアの最小値。但し、
$j=0$ の時、辺 $i$ は削除されている
$j=1$ の時、辺 $i$ は残っている

遷移について、辺 $i-1$ 番目が決定しているとして、辺 $i$ を考えます。

辺 $i$ を残す場合
辺 $i-1$ は削除されていても残っていてもよいです。従って、
$dp[i][1]\leftarrow min(dp[i-1][0],dp[i-1][1])+A_i$
辺 $i$ を削除する場合
辺 $i-1$ は残っている必要があります。そうしないと、頂点 $i$ の次数が0になります、従って、
$dp[i][1]\leftarrow dp[i-1][1]$

このように遷移していけば解けるかのように思えますが、例えば、 $i=0$ の時の初期値を

$dp[0][1]\leftarrow A_0$
$dp[0][0]\leftarrow 0$

として、 $i=2,...,N-1$ と更新していくと $i=N-1$ で困ったことになります。というのも、

辺 $N-2$ が存在する場合でも、辺 $0$ が存在しない場合には辺 $N-1$ を残さなければならず、前述の遷移通りいきません。

これを解決するためには辺 $0$ が残っているかどうかの情報があれば良いので、DPテーブルに追加します。

$dp[i][j][k]:=$ 辺 $i$ の状態が $j$ であり、かつ、辺 $0$ の状態が $k$ の時のスコアの最小値。但し、
$j=0$ の時、辺 $i$ は削除されている
$j=1$ の時、辺 $i$ は残っている
$k=0$ の時、辺 $0$ は削除されている
$k=1$ の時、辺 $0$ は残っている

遷移は、 $k=0,1$ の両方の場合が必要になるだけで、先程と同じです。

辺 $0$ を初期値とします。
$dp[0][0][0] \leftarrow 0$
$dp[0][1][1] \leftarrow A_0$
$dp[0][0][1] \leftarrow \infty$
$dp[0][1][0] \leftarrow \infty$
としておきます。( $dp[0][0][1],dp[0][1][0]$ は矛盾しており、あり得ない状況です。)

このDPを $1,...,N-2$ まで順に更新します。
辺 $N-1$ の状態は、辺 $0,N-2$ の状態に従います。

辺のいずれか一方が削除されている場合
頂点 $0,N-2$ の少なくとも一方は次数0なので、辺 $N-1$ は残す必要があります。よって、この時は、
$x_1 = min(dp[N-2][0][0],dp[N-2][0][1],dp[N-2][1][0])+A_i$
辺の両方がある場合
頂点 $0,N-2$ の両方とも次数が1なので、辺 $N-1$ は不要です。よって、この時は、
$x_2 = dp[N-2][1][1]$

最終的な答えは、 $min(x_1,x_2)$ です。
提出コード