[AtCoder] ARC 007 C – 節約生活

問題

方針

\( i \) から \( i + 1 \) 分が視聴できる状態をビットを用いて、\( i \) ビット目が \( 1 \) であるとします。そうでないときは \( 0 \) です。

与えられた文字列を、\( a_i = 0 \) または \( a_i = 1 \) として、

\[ b_1 = a_1a_2 \cdots a_n \]

とします。 \( 1 \) 分ずらしてテレビをつけると、

\[ b_2 = a_2a_3\cdots a_{n}a_1 \]

というビットが得られます。したがって、時間をずらして得られるビットは \( n \) 通りあります。ここで、テレビの視聴可能な時間の状態 \( i \) のときの必要なテレビの最小値を \( d(i) \) とします。考えられる状態は \( 2^n \) 通りあり、\( d(0) = 0 \) とし、その他は \( \infty \) とします。更新式は、

\[ d(i \lor b_j) \leftarrow \min(d (i \lor b_j) , d(i) + 1)\]

となります。

コード