Codeforces #559 (Div. 2) D問題 : The minimal unique substring

問題. The minimal unique substring

文字列の部分文字列に対して，その部分文字列の出現回数がちょうど1回のときユニークな部分文字列と呼ぶ．正整数 $n, k$ が与えられる．ただし， $n \equiv k \pmod 2$ とする．0 と 1 からなる長さ $n$ の文字列で，ユニークな部分文字列の長さの最小値が $k$ となる文字列を構成せよ．

制約： $1 \le k \le n \le 10^5$

解法

Codeforces Round #559 — editorial - Codeforces を参考にした．

$a = \frac{n - k}{2}$ とする．このとき， $n \equiv k \pmod 2$ から $a$ は非負整数となる．構成する文字列を $s_1 s_2 \ldots s_n$ として，添字番号が $a + 1$ の倍数のとき 1 として，それ以外のとき 0 とする．このとき， $t = s_{a + 1} s_{a + 2} \ldots s_{a + k}$ が長さ $k$ のユニークな部分文字列となり，長さ $k - 1$ 以下のどの部分文字列の出現回数も 2 以上となる．

まず， $k \le n$ から $a + k \le n$ なので部分文字列 $t$ が存在する．また， $s_{a + 1}$ は 1 となる文字で一番左あるので， $t$ がユニークでないとすると $t$ と等しく最も左にある部分文字列は $s_{2 a + 2} s_{2 a + 3} \ldots s_{2a + k + 1}$ となる（∵ 周期が $a + 1$ ）．しかし， $2a + k + 1 > n$ なのでそのような部分文字列は存在しない．したがって， $t$ は長さ $k$ のユニークな部分文字列となる．

次に，長さ $k - 1$ 以下のユニークな部分文字列が存在しないことを示す． $2 \le k$ ならば $1$ は2つ以上存在するので，0 のみからなる部分文字列の出現回数は 2 以上となる．また， $2a + k \le n$ なので，1 を含むよな長さ $k - 1$ 以下の部分文字列の出現回数は 2 以上となる．

計算時間： $O(n)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    int a = (n - k) / 2;
    for (int i = 1; i <= n; ++i)
        cout << (i % (a + 1) == 0);
    cout << endl;

    return 0;
}

~~どう思いつけばいいのかは何となくしか分からないので課題．~~ 👉 考え方として，長さが小さいものから大きいものを構成する方法が考えられるけど上手くいかなかった（長さが奇数のときはこの考えで構成できた）． $k \le 2$ のとき，0 のみからなる文字列には 1 が必要で，しかも $k \le 2$ から 2 つ以上必要．何となく周期的になっているので 1 を入れる箇所を周期的に考えて，必要条件（上の証明のようなもの）を列挙して $a$ を導いて，十分条件も満たすことを示す・・・という流れだと思うけど難しい．
実験的に考察するのも手だと思うのでそれも考慮してみる．