JOI14春合宿3-1 JOIOJI (6)

https://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d3.pdf
(問題PDFのURL)

概要

J, O, I からなる長さNの文字列が与えられる。この文字列の（連続する）部分文字列の中で、J, O, Iの数が等しい部分文字列の最大の長さを求めよ。

制約

N ≦ 2*10^5

方針

str[s : t] ：文字列strのs文字目からt文字目の部分文字列（len(str[s : t]) = t - s + 1）
J[t], O[t], I[t]：それぞれ、1文字目からt文字目までのJの数、Oの数、Iの数　とする。
str[s : t]のJ, O, Iの数が等しい ⇔ J[t] - J[s-1] = O[t] - O[s-1] かつ J[t] - J[s-1] = I[t] - I[s-1]
よって、愚直にはs, tの全探索で上記の条件を満たすt, sについて、t - s + 1の最大値を出力する。
ただし、これだとO(N^2)となり、間に合わない。

J[t] - J[s-1] = O[t] - O[s-1] かつ J[t] - J[s-1] = I[t] - I[s-1]　… Aを
J[t] - O[t] = J[s-1] - O[s-1] かつ J[t] - I[t] = J[s-1] - I[s-1] と移行する。
a[t] = J[t] - O[t], b[t] = J[t] - I[t] とおくと、Aの条件は

a[t] = a[s-1] かつ b[t] = b[s-1] … B

と書き換えることができる。

Bの条件を満たす最長のt - s + 1は尺取り法を用いた以下の手順でO(NlogN)で計算することができる。

• a, b, idxをセットにした構造体を定義する(pos)
• a, b, idxの優先順に昇順ソートする
• x, yを準備し、pos[x].a = pos[y].a, pos[x].b = pos[y]となる間yを進める。その間pos[y].idx - pos[x].idxの最大値を更新する。
• (pos[x].a = pos[y].a, pos[x].b = pos[y])でなくなったら、xをyとする。

解答

模範解答のコピペ。。
Submission #9593351 - 2014年 日本情報オリンピック春合宿 オンラインジャッジ

/*
	Sort then Shakutori (O(N log N))
*/
#include <bits/stdc++.h>
 
using namespace std;
 
struct Pos {
	int jo;
	int ji;
	int len;
 
	bool operator < (const Pos &other) const {
		if (jo != other.jo) return jo < other.jo;
		if (ji != other.ji) return ji < other.ji;
		return len < other.len;
	}
};
 
int chmax(int &a, int n) {
	if (n > a) a = n;
	return a;
}
 
int main() {
	int N;
	string S;
	cin >> N >> S;
 
	vector<Pos> ois;
	Pos origin;
	origin.jo = origin.ji = origin.len = 0;
	ois.push_back(origin);
 
	int Js = 0, Os = 0, Is = 0;
	for (int i = 0; i < N; i++) {
		char c = S[i];
		if (c == 'J') Js++;
		else if (c == 'O') Os++;
		else Is++;
 
		Pos pos;
		pos.jo = Js - Os;
		pos.ji = Js - Is;
		pos.len = i + 1;
 
		ois.push_back(pos);
	}
	sort(ois.begin(), ois.end());
 
	int ans = 0;
	int lastind = 0;
	for (int i = 1; i < ois.size(); i++) {
		if (ois[i].jo == ois[lastind].jo && ois[i].ji == ois[lastind].ji) {
			chmax(ans, ois[i].len - ois[lastind].len);
		}
		else {
			lastind = i;
		}
	}
 
	cout << ans << endl;
	return 0;
}