Codeforces Round #562 (Div. 1) : B. Good Triple

https://codeforces.com/contest/1168/problem/B

問題概要

各文字が0または1のどちらかからなる長さNの文字列Sが与えられる。1 <= l <= r <= N を満たす整数の組(l, r)のうち、Sの区間[l, r]の中に同じ文字が3文字以上等間隔で並んでいるものの数を求めよ。

N <= 3×105

解法

なんかこの条件を満たさないのはすごい難しいんじゃないかと考えて小さいNで実験コードを書いてみると10文字以上くらいになると必ず条件を満たす3文字が存在してしまうことがわかる。よって長さ10程度までの区間を全探索して条件を満たさないものを全選び方の総数から引けばよい。

感想

本番中、実験まではやっていたのになぜかそこから全探索にいかず(かなしいね)

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

void main(){
    auto S = readln.chomp;
    auto N = S.length.to!int;
    long ans = 1L * N * (N + 1) / 2;

    foreach (l; 0..N) foreach (r; l..min(N, l+10)) {
        bool ok = true;
        foreach (i; l..r+1) for (int j = 1; i - j >= l && i + j <= r; ++j) {
            if (S[i-j] == S[i] && S[i] == S[i+j]) ok = false;
        }
        ans -= ok;
    }

    ans.writeln;
}