#1193140 (D) No.2298 yukicounter

• 問題: No.2298 yukicounter
• ユーザー: InTheBloom
• 提出日時: 2026-10-15 12:35:31
• 言語: D (dmd 2.113.0)
• 結果: AC
• 実行時間: 133 ms / 2,000 ms
• コード長: 4,537 bytes
• コンパイル時間: 2,824 ms
• コンパイル使用メモリ: 189,736 KB
• 実行使用メモリ: 31,792 KB
• 最終ジャッジ日時: 2026-10-15 12:35:42
• 合計ジャッジ時間: 5,567 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge5_0

ファイルパターン	結果
sample	AC * 3
other	AC * 32

ソースコード

import std;

void main () {
    string S = readln.chomp;
    const int N = S.length.to!int;

    string y = "yukicoder";
    const int M = y.length.to!int;

    bool f (int x) {
        string pat = replicate(y, x);

        string X = pat ~ S;
        auto z = zAlgorithm(X);

        foreach (i; pat.length .. z.length) {
            if (pat.length <= z[i]) {
                return true;
            }
        }
        return false;
    }
    auto ret = bsearch!(f)(0, (N + M - 1) / M);

    writeln(ret.value);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

int[] zAlgorithm (T) (const T[] S) {
    const int N = cast(int) S.length;
    auto ret = new int[](N);
    if (N == 0) {
        return ret;
    }
    ret[0] = N;

    int i = 1, j = 1;
    // S[0 .. j - i) = S[i .. j)を保つ。

    while (i < N) {
        if (j < i) {
            j = i;
        }

        // LCPを広げる。
        while (j < N) {
            if (S[j - i] != S[j]) {
                break;
            }
            j++;
        }
        ret[i] = j - i;

        // 計算を再利用する。
        int k = 1;
        while (k <= i && i + k < j && i + k + ret[k] < j) {
            ret[i + k] = ret[k];
            k++;
        }

        i += k;
    }

    return ret;
}

unittest {
    import std.algorithm: equal;
    assert(equal(zAlgorithm("abcbcba"), [7, 0, 0, 0, 0, 0, 1]), "test1");
    assert(equal(zAlgorithm("mississippi"), [11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), "test2");
    assert(equal(zAlgorithm("ababacaca"), [9, 0, 3, 0, 1, 0, 1, 0, 1]), "test3");
    assert(equal(zAlgorithm("aaaaa"), [5, 4, 3, 2, 1]), "test4");
    assert(equal(zAlgorithm(""), new int[](0)), "test5");
}

import std.traits : isIntegral;
import std.int128 : Int128;

class NoTrueRangeException: Exception {
    import std.exception: basicExceptionCtors;
    mixin basicExceptionCtors;
}

class BsearchException: Exception {
    import std.exception: basicExceptionCtors;
    mixin basicExceptionCtors;
}

struct BsearchResult (T) {
    import std.format: format;

    private bool has_value = true;
    private T l, r;
    private T _value;

    this (T _l, T _r) {
        this.l = _l;
        this.r = _r;
        this.has_value = false;
    }
    this (T _l, T _r, T _value) {
        this.l = _l;
        this.r = _r;
        this._value = _value;
    }

    bool empty () {
        return !this.has_value;
    }

    T value () {
        if (this.empty()) {
            throw new NoTrueRangeException(
                    format("No true condition found in the range [%s, %s].", l, r));
        }

        return _value;
    };
}

BsearchResult!T bsearch (alias func, T) (T l, T r)
if ((isIntegral!(T) || is(T == Int128)) &&
        !is(T == byte) &&
        !is(T == ubyte) &&
        !is(T == short) &&
        !is(T == ushort))
{
    import std.traits : isCallable, ReturnType, Parameters;
    import std.meta : AliasSeq;

    static assert(isCallable!(func));
    static assert(is(ReturnType!(func) == bool));
    static assert(is(Parameters!(func) == AliasSeq!(T)));

    import std.algorithm.comparison : min, max;
    T L = l, R = r;

    if (l == r) {
        if (func(l)) return BsearchResult!(T)(L, R, l);
        return BsearchResult!(T)(L, R);
    }

    while (min(l, r) + 1 < max(l, r)) {
        T m = midpoint(l, r);

        if (func(m)) {
            l = m;
        }
        else {
            r = m;
        }
    }

    bool lb = func(l);
    if (!lb) return BsearchResult!(T)(L, R);

    bool rb = func(r);
    if (rb) return BsearchResult!(T)(L, R, r);
    if (!rb) return BsearchResult!(T)(L, R, l);

    throw new BsearchException(format("This code path should never be reached. l: %s, r: %s.", L, R));
}

T midpoint (T) (T a, T b)
if (isIntegral!(T) || is(T == Int128))
{
    static if (is(T == short) || is(T == ushort) || is(T == byte) || is(T == ubyte)) {
        import std.conv : to;
        int x = a, y = b;
        return midpoint(x, y).to!(T);
    }
    else {
        import std.math.algebraic : abs;
        import std.algorithm.comparison : min, max;
        
        int as = (0 <= a) ? 1 : -1, bs = (0 <= b) ? 1 : -1;
        if (as == bs) {
            if (as == 1) {
                return min(a, b) + (max(a, b) - min(a, b)) / 2;
            }
            return max(a, b) + (min(a, b) - max(a, b)) / 2;
        }

        return (a + b) / 2;
    }
}