けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

TopCoder SRM 452 DIV1 Medium - IOIString (本番 19 人)

すごく面白かった!

スコア: 191.85 / 500.00

問題概要

"I" と "O" のみからなる文字列  T が IOI 文字列であるとは、ある正の整数  a, b が存在して

  •  T_{a} = "I"
  •  T_{a+b} = "O"
  •  T_{a+2b} = "I"

が成立することと定義する (1-indexed)。

いま、"I", "O", "?" のみから成る文字列  S が与えられる。 S の各 "?" を "I" か "O" に置き換える方法のうち、IOI 文字列となるものの個数を 1000000007 で割ったあまりを求めよ。

制約

  •  1 \le |S| \le 2500

考えたこと

面白そう!!!

現代の典型思考方法としては、まずは IOI 文字列の条件をわかりやすく言い換えること。今のままじゃ数えづらいので。また、IOI 文字列を特徴付けるよりも、補集合をとって「IOI 文字列でないための条件」を考えることにする。

まず自明な必要条件として、

  • "IOI" を連続部分文字列として含んだらダメ
  • "IOOOI" を連続部分文字列として含んだらダメ
  • 一般に "I (奇数個の O) I" を連続部分文字列として含んだらダメ

ということが言える。よって、文字列  S 中の "I" の index を  a_{1}, a_{2}, \dots, a_{K} としたとき、この数列の連続する 2 項の差が奇数でなければならないことが言える。さらに、

  •  a が交差が奇数の等差数列でなければならない

ということも言える。もし  a_{i+1} - a_{i} = a_{i} - a_{i-1} となるような箇所が存在すると仮定すると、

  •  a_{i+1} - a_{i-1} は偶数
  •  a_{i-1}, a_{i+1} の中点は "O" となる

となっているのでダメなのだ。たとえば "IOOOIOOOOOI" を想像してみるといい。これは IOI 文字列となってしまっている。

逆に、 a が交差奇数の等差数列であれば、それは IOI 文字列ではない。以上で、わかりやすく特徴付けられた。

数え上げ

"?" の個数を  Q として、"?" を埋める  2^{Q} 通りの方法のうち、IOI 文字列とならないものを数えることにする (全体から引いたものを答える)。

  • 交差  d を固定
  • "I" の index を表す数列  a の初項  a_{1} を固定

としたときに (ここまでで  O(N^{2}))、数列  a の長さ  K が何通りあるかを考えることにする。条件は

  • 文字列  S a_{1} 番目より左側に "I" がない
  • 文字列  S a_{i} 番目と  a_{i+1} 番目の間に "I" がない
  • 文字列  S a_{K} 番目より右側に "I" がない

と表せる。これは予め累積和を管理することで高速に判定できる。

さて、 K としてありうるものは  O(\frac{N}{d}) 通りしかないことに注意すると、全体の計算量は「調和級数の和のオーダー解析」の要領で  O(N^{2} \log N) となる。十分間に合う。

コード

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
class IOIString {
public:
    int countIOIs(vector <string> mask) {
        string str = "";
        for (auto s: mask) str += s;
        int N = (int)str.size();
        vector<int> inum(N+1, 0), qnum(N+1, 0);
        for (int i = 0; i < N; ++i) {
            inum[i+1] = inum[i], qnum[i+1] = qnum[i];
            if (str[i] == '?') ++qnum[i+1];
            else if (str[i] == 'I') ++inum[i+1];
        }
        vector<long long> two(qnum.back()+1, 1);
        for (int i = 0; i < qnum.back(); ++i) two[i+1] = two[i] * 2 % MOD;

        // 余事象を数える
        long long all = two.back(), sub = 0;

        // I が 0 個
        if (inum.back() == 0) ++sub;

        // I が 1 個
        for (int i = 0; i < N; ++i) {
            if (str[i] != 'O' && inum[i] == 0 && inum.back() - inum[i+1] == 0) ++sub;
        }

        // I が 2 個以上で、交差奇数の等差数列
        for (int d = 1; d <= N; d += 2) {
            for (int i = 0; i < N; ++i) {
                if (str[i] == 'O' || inum[i] > 0) continue;
                int prev = i+1;
                for (int j = i + d; j < N; j += d) {
                    if (str[j] == 'O') break;
                    if (inum[j] - inum[prev] > 0) break;
                    if (inum.back() - inum[j+1] == 0) ++sub;
                    prev = j+1;
                }
            }
        }  
        long long res = (all - sub + MOD) % MOD;
        return res;
    }
};