https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d
解説
https://atcoder.jp/contests/sumitrust2019/submissions/8776950
3桁を指定するのはO(N3)かかってしまう。
だが、答えの組み合わせに注目してみると、103通りある。
これなら全探索できるので、103通りで作れるかどうか試してみる。
全ての文字について、次にある文字が出てくる最近の添字を覚えておく。
すると、先頭から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; }