Educational Codeforces Round 101 - E. A Bit Similar - 輪郭をなぞるだけのブログ

酒入ってたけど、入ってなくても思いつかなかったな。

問題概要

$2$ つの $01$ 文字列で $1$ 文字でも一致する状態を "a bit similar" であるとする。
文字列 $s$ が与えられたとき、 $s$ から得られる長さ $k$ の部分文字列すべてに対して "a bit similar" である辞書順最小の $k$ 文字の文字列を求める。(なければ "NO" と答える。)
テストケースは $q$ 個与えられる。
補足 : 部分文字列は、文字列の連続する部分列のことである。

制約

$1 \leq q \leq 10000$
$1 \leq k \leq n (=|s|) \leq 10^6$
$\sum n \leq 10^6$

解法

$0$ と $1$ を反転した文字列を考える。
この文字列に現れる長さ $k$ の部分文字列は、題意を満たさないと言える。

例えば、"0110" を反転させた "1001" を見てみる。( $k=2$ とする。)
$k=2$ 文字ずつスライドしてみていくと、
0110
1001

0110
1001

0110
1001
となっていて、反転前の部分文字列を見ると "a bit similar" でないので、確かに題意を満たさない。
ただ、 $01$ 文字列を考えているので、それぞれ $1$ 文字でも異なっていれば、"a bit similar" でなかったものは "a bit similar" となる。
このことから、反転させた文字列から取れる部分文字列に含まれていない長さ $k$ の文字列は、題意を満たす。

したがって、出現した部分文字列を管理して、出現しなかった辞書順最小のものを答えとすればよい。(すべて出現していれば "NO" となる。)
( $2$ 進表記で見ると、mex (集合に含まれない最小の数) を $[0, 2^k)$ の範囲内で求めることと同じ。)

ただ、そのまま実装にうつると、部分文字列の列挙に $O(nk)$ かかって大変なことになるので、もう一工夫する必要がある。

部分文字列の個数は $n - k + 1$ 個あるが、この個数は制約から $2^{20}(>10^6)$ で抑えられる。
よって、 $k>20$ の場合は先頭 $k-20$ 文字を $0$ で埋めても問題はない。(自由度を下位 $20$ 桁に制限しても、 $2^{20}$ 通りあるので、必ず解が存在して "YES" となる。)
考慮すべきなのは、先頭 $k-20$ 文字が $0$ である部分文字列の下位 $20$ 文字であり、これを集合に追加すればよい。(先頭に $1$ が含まれていれば、その時点で求めようとしている文字列と反転前の部分文字列とは "a bit similar" になるので、考慮する必要はない。)

コード

#include <iostream>
#include <string>
#include <set>
#include <vector>
using namespace std;

void solve(){
    int n, k;
    string s;
    cin >> n >> k >> s;
    
    // '0' '1' 反転
    for(int i = 0; i < n; ++i) s[i] = s[i] == '0' ? '1' : '0';
    
    // 出現した部分文字列を 2 進数として集合で管理
    set<int> st;
    if(k <= 20){
        for(int i = 0; i + k <= n; ++i){
            st.emplace(stoi(s.substr(i, k), nullptr, 2));
        }
    }
    else{
        vector<int> zeros(n + 1);
        for(int i = 0; i < n; ++i){
            zeros[i + 1] = zeros[i] + (s[i] == '0');
        }
        for(int i = 0; i + k <= n; ++i){
            // 先頭 (k - 20) 文字が 0 で埋まっていれば、集合に要素を追加
            if(zeros[i + k - 20] - zeros[i] == k - 20){
                st.emplace(stoi(s.substr(i + k - 20, 20), nullptr, 2));
            }
        }
    }
    
    // mex を求める
    int ans = -1;
    for(int num = 0; num < 1 << min(k, 20); ++num){
        // num が集合になければ ans を保存してループを抜ける
        if(st.find(num) == st.end()){
            ans = num;
            break;
        }
    }
    
    if(ans == -1) cout << "NO\n";
    else{
        cout << "YES\n";
        for(int i = 0; i < k - 20; ++i) cout << 0;
        for(int i = min(k, 20) - 1; i >= 0; --i) cout << (ans >> i & 1);
        cout << '\n';
    }
}

int main(){
    int q;
    cin >> q;
    while(q--) solve();
    return 0;
}

雑記

コンテスト後に解法ツイートを眺めていたが、どうしてビット列を反転させているのかしばらく分からなかった。
難しい。