[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)\]
となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } int main() { string s; cin >> s; int n = s.length(); int b[n]{}; for (int i = 0; i < n; i++) { if (s[i] == 'o') { b[0] += (1<<i); } } int m = 1 << n; int mask = m - 1; for (int i = 1; i < n; i++) { b[i] = (b[i - 1] << 1) & mask; if (b[i - 1] & (1<<(n - 1))) { b[i]++; } } int d[m]{}; fill(d, d + m, 100); d[0] = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (d[i] == 100) continue; int id = i | b[j]; chmin(d[id], d[i] + 1); } } cout << d[m - 1] << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません