SRM 452 div1 med: IOIString - mayoko’s diary

IOI

問題

解法

IOIString でない string の数を数えることにします。

まず, 全部 O で構成されているような string は IOIString ではないです。
また, I がひとつだけ存在する string も IOIString ではないです。
I が２つある string は, I の登場する座標が x, y であったとすると, x と y の偶奇が一致しない場合のみ, IOIString ではないです。
I が 3 つある string は, I の登場する座標が x, y, z であったとすると, x と y, x と z, y と z の座標が一致しないことがまず第一条件です。ただ, こうすると x と z の偶奇は一致しています。しかし, y = (x+z)/2 であったとすると, IOI は構成されないので, y = (x+z)/2 も満たせば IOIString ではないです。

I が 4 つ以上ある場合も同じように, x[0], x[1], ..., x[m] が偶奇交互, x[i] = (x[i-1]+x[i+1])/2 となれば良いです。
このような non-IOIString は O(N^2 log N) で数え上げることが出来ます。

I が始まる位置 start と, I の感覚 d(これは奇数) を決めて, start 〜 start+n*d が入力からありえるなら non-IOIString の数が 1 増える, というのを正直に回すと, start と d の決め方で O(N^2), start 〜 start+n*d の n の候補が 1/1 + 1/2 + ... + 1/n となるので O(log N) で計算できます。

文字列中の I の数に注目する感じで「入力から考えている文字列がありえるか」を考えています。詳しいことはコード参照。

const int MOD = 1e9+7;

class IOIString {
public:
    int countIOIs(vector <string> mask) {
        string s;
        for (string t : mask) s += t;
        int n = s.size();
        if (n <= 2) return 0;
        int ans = 1, icnt = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '?') (ans *= 2) %= MOD;
            else if (s[i] == 'I') icnt++;
        }
        int minus = 0;
        for (int d = 1; d < n; d+=2) {
            for (int start = 0; start < n; start++) {
                int cnt = 0;
                for (int j = 0; start+j*d < n; j++) {
                    if (s[start+j*d] == 'I') cnt++;
                    else if (s[start+j*d] == 'O') break;
                    if (cnt == icnt) {
                        if (d != 1 && j == 0) continue;
                        minus++;
                    }
                }
            }
        }
        cout << minus << endl;
        if (!icnt) minus++;
        cout << minus << endl;
        ans = (ans-minus+MOD)%MOD;
        return ans;
    }
};