Lucky PIN [Sumitomo Mitsui Trust Bank Programming Contest 2019 D]

https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

解説

https://atcoder.jp/contests/sumitrust2019/submissions/8776950

3桁を指定するのはO(N³)かかってしまう。
だが、答えの組み合わせに注目してみると、10³通りある。
これなら全探索できるので、10³通りで作れるかどうか試してみる。
全ての文字について、次にある文字が出てくる最近の添字を覚えておく。
すると、先頭から3つの数を貪欲に探していくのをO(1)できる。
自分はこのへんはライブラリにしてるので、貼るだけ。

int N; string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;

    fore(c, S) c -= '0';
    StringMaster sm(S);

    int ans = 0;
    rep(x0, 0, 10) rep(x1, 0, 10) rep(x2, 0, 10) {
        int cu = -1;
        cu = sm.gomigi(cu, x0);
        cu = sm.gomigi(cu, x1);
        cu = sm.gomigi(cu, x2);
        if (cu < inf) ans++;
    }
    cout << ans << endl;
}