AtCoder Regular Contest 007 C - 節約生活

問題

　テレビを点けた瞬間から数えて視聴可能なタイミングを'o'、不可能なタイミングを'x'で表す文字列が与えられる。同じテレビを複数用意し点けるタイミングをずらすことで、最後のテレビを点けて以降はどの瞬間もいずれかのテレビで視聴可能であるようにしたい。最低必要な台数を求めよ。

解法

　最大でも $N$ 個使えば視聴可能になる。点ける時刻は $\mathrm{mod}\;N$ で考えればいいので各 $N$ 通り。二つ以上のテレビを同じ時刻で点ける意味はないことから、全探索しても計算量は $O(N!)$ で済む。

反省

　33分でAC。解法自体はすぐにわかったが、その実装をどうすればいいのかに悩んでしまった。大きく分けると

点ける時刻の組み合わせを列挙する方法
ある点ける時刻の組が条件を満たしているか判定する方法

　という2つの山があるように思う。前者は点ける時刻の配列を後ろから見ていき、 $N - 1$ 未満だったらそこを $+1$ して、そこから以降を前のもの $+1$ したものにしていくという実装にした。順番を無視できるタイプの組み合わせを列挙する問題で何度か書いた経験があるがいまだに慣れず、書き出すのに抵抗を感じてしまう。

　後者はビット演算で実装した。点ける時刻分だけシフトしたパターンの $or$ を取っていき、最終的に時刻 $N + 1$ から $2N$ まで全部ビットが立っているかを判定することでなんとかできた。

　パッと思いついた実装が面倒くさそうだったのでもうちょっと良さそうな実装を探りながら……という感じだったが結局あまり簡単にはできなかった。他の人の解法を考えると、ある時刻分ずらしたものを採用するかどうかを考えていけば $O(2^{N})$ で解けたようだ。こういう考え方がなかなかできてこない。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

ll N;

bool next(vector<ll>& v) {
    for (ll i = v.size() - 1; i >= 0; i--) {
        if (v[i] >= (N - 1) - (v.size() - i)) {
            //これ以上増やせない
            continue;
        }

        //iを増やし、i以降を前のもの+1にする
        iota(v.begin() + i, v.end(), v[i] + 1);
        return true;
    }
    return false;
}

int main() {
    string c;
    cin >> c;

    N = c.size();

    ll bit = 0;
    for (ll i = 0; i < N; i++) {
        if (c[i] == 'o') {
            //2ループ分ビットを立てる
            bit ^= (1LL << i);
            bit ^= (1LL << i + N);
        }
    }

    //テレビを点けるのは[0, N)の間なので
    //[N, 2N)で全部ビットが立っていれば良い
    ll target = (((1 << N) - 1) << N);

    for (ll i = 1; i <= N; i++) {
        //i台で可能かを判定
        vector<ll> tv(i, 0);
        iota(tv.begin(), tv.end(), (ll)0);

        while (true) {
            ll all = 0;
            for (ll j = 0; j < i; j++) {
                all |= (bit << tv[j]);
            }

            if ((target & all) == target) {
                cout << i << endl;
                return 0;
            }

            if (!next(tv)) {
                break;
            }
        }
    }
}