[Codeforces] Hello 2019 B. Petr and a Combination Lock

Petr and a Combination Lock

https://codeforces.com/contest/1097/problem/B

動的計画法かbit全探索の問題です。

考え方

題意

\( 360 \) 度を示すことができる角度計において、配列の要素の値の分だけ時計回りか反時計回りに矢印を動かすことを考えます。初期値が原点の \( 0 \) 度であり、\( n \) 回矢印を動かし終わったとき、原点に戻ってくることができるかを調べます。

方針

配列の各要素にたいして、時計回りか反時計回りかの \( 2 \) 通りの操作を行うことが考えられるので、動的計画法かbit全探索を行って解答を得ることができます。ここでは、動的計画法を使ってみます。

\( dp[i][j] = 1\) を \( i \) 個目まで配列を調べたときに矢印が \( j \) 度であることを表します。また、\( dp[i][j] = 0\) は矢印がそこにいないことを表すとします。初期値は \( 0 \) なので、\( dp[0][0] = 1\) です。

ここで、\(dp[i][j] = 1 \) のとき、

\( dp[i + 1][(j + a[i]) \mod 360] = 1 \)、

\( dp[i + 1][(j – a[i] + 360) \mod 360] = 1 \)

とします。そして、\( dp[n][0] = 1\) ならば原点に戻ってくることができます。

コード

感想

動的計画法の典型的な問題だと思いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする