https://beta.atcoder.jp/contests/cf16-tournament-round1-open/tasks
にぶたんします。
結局任意のi,jに対してS[i...i+M]とS[j...j+M]が高速に比較できればいいんですが、これはsuffix arrayでできます。
suffix array知っていれば一瞬の問題なのかぁ。
部分列の比較ならsuffix arrayと思えば良さそう。
int N, K, M; vector<int> S; int ran[MAX_N]; vector<int> ord; SA sa; bool ok(int m) { int pat = ord[m]; int cnt = 1; int at = 0; while(N - at >= M) { if(ran[at] <= ran[pat]) { at += M; } else { if(M == 1) return false; at += M - 1; } if(at == N) break; cnt++; } return cnt <= K + 1; } void solve() { cin >> K; string str; cin >> str; N = sz(str); S.resize(N); rep(i, 0, N) S[i] = str[i] - '0'; sa.init(S, 10); M = (N + (K + 1) - 1) / (K + 1); rep(i, 1, N) { int a = sa.sa[i], b = sa.sa[i + 1]; if(sa.lcp[i] >= M) ran[b] = ran[a]; else ran[b] = ran[a] + 1; } rep(i, 1, N + 1) { if(sa.sa[i] < N - M + 1) ord.pb(sa.sa[i]); } int lv = -1, uv = N - M; while(uv - lv > 1) { int m = (lv + uv) / 2; if(ok(m)) uv = m; else lv = m; } string ans; int at = ord[uv]; rep(i, 0, M) ans += S[at + i] + '0'; cout << ans << "\n"; }