問題文がシンプルで良い。
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した人そこまで多くないから、そこまで自明ではないのかな。