CODE FESTIVAL 2016 Elimination Tournament Round 1,B: 数字列をカンマで分ける問題

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";
}