[AtCoder] ARC 007 C – 節約生活

2020年12月12日

問題

方針

\( 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;
}