kmjp's blog

競技プログラミング参加記です

Codeforces #683 Div1 D2. Frequency Problem

問題文がシンプルで良い。
https://codeforces.com/contest/1446/problem/D2

問題

整数列Aが与えられる。
この連続部分列のうち、再頻出の値が同着で2個以上あるようなケースについて、最長の長さを求めよ。

解法

A全体において、再頻出の値が同着で2個以上ある場合、A全体を答えればよい。
そうでない場合、再頻出の値をDとすると、解となる連続部分列ではそこでもDが再頻出となるものが存在する。

そこで、Dと別の値Vが再頻出となるようなケースを総当たりしよう。
もし、その中でDでもVでもない値Wが再頻出になったとしても、別途DとWが再頻出になるケースで回収されるので問題ない。

もしVの登場頻度が多い場合、AをD・V・それ以外に分類して、DとVの登場頻度が一致する箇所を洗い出せばよい。
これは整合性のとれた括弧列と同じ手順で処理できる。
Vの登場頻度が少ない場合、部分列に含む最初と最後のVを総当たりしてそこに含まれうるDの数を数えて行けばよい。

int N;
int A[202020];
vector<int> P[202020];
set<int> S;
int id[404040];
int pos[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		P[A[i]].push_back(i);
	}
	
	int ma=0,num=-1;
	FOR(i,N) ma=max(ma,(int)P[i].size());
	x=-1;
	FOR(i,N) if(P[i].size()==ma) {
		if(x==-1) {
			x=i;
			FORR(p,P[i]) S.insert(p);
		}
		else {
			cout<<N<<endl;
			return;
		}
	}
	MINUS(id);
	S.insert(N);
	int ret=0;
	FOR(i,N) {
		if(i==x||P[i].empty()) continue;
		if(P[i].size()<=400) {
			FORR(p,P[i]) S.insert(p);
			FORR(p,P[i]) {
				auto it=S.find(p);
				map<int,int> M;
				int cur=0;
				FOR(j,P[i].size()+1) {
					if(it==S.begin()) {
						M[cur]=0;
						break;
					}
					it--;
					M[cur]=*it+1;
					if(A[*it]==x) cur--;
					if(A[*it]==i) break;
				}
				it=S.find(p);
				cur=0;
				FOR(j,P[i].size()*2+1) {
					y=*it;
					if(M.count(cur)) ret=max(ret,y-M[cur]);
					if(y==N) break;
					if(A[y]==x) cur++;
					else cur--;
					it++;
				}
			}
			FORR(p,P[i]) S.erase(p);
		}
		else {
			int cur=202020;
			id[cur]=i;
			pos[cur]=0;
			FOR(j,N) {
				if(A[j]==i) cur++;
				if(A[j]==x) cur--;
				if(id[cur]==i) ret=max(ret,j+1-pos[cur]);
				else id[cur]=i, pos[cur]=j+1;
			}
		}
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

「再頻出の値をDとすると、解となる連続部分列ではそこでもDが再頻出となるものが存在する」に気付くかどうか。
この特性そんな自明なのかな…。本番中にACした人そこまで多くないから、そこまで自明ではないのかな。