これは解けても良かったな。
https://codeforces.com/contest/2230/problem/F
問題
木を成す無向グラフを使った2人ターン制のゲームを考える。
初期状態で全点は白い。
先手は、初回は任意の場所にコマを置きその点を赤く塗る。以降は、隣接する白マスのうち1つを選びコマを移動してその点を青く塗る。
後手は、任意の白マスを青く塗る。
先手は赤マスを最大化、後手は最小化するとき、赤マスは何マスになるか。
木に徐々に点を追加していくクエリが与えられるので、そのつど上記ゲームの解を答えよ。
解法
クエリは置いておいて、まず1つの木における解を考える。
先手がSubTreeのうちどこに行こうとするかを考えると、後手は赤マスが最大となる子頂点をつぶしに来るので、先手は2番目に赤マスが増える子頂点を選ぶ。
よって、各点から子頂点に遷移したときに得られる赤マスの最大値3個まで持って、全方位木DPすればよい。
また、この問題の解はクエリに対し単調増加で、かつ高々O(log(頂点数))程度の値になる。
よって二分探索の要領で、同じ解になる範囲を求めることで、全方位木DPの回数を削減できる。
int Q; vector<int> E[202020]; int ret[202020]; int dp1[202020],dp2[202020],dp3[202020]; int M; int dfs2(int cur,int pre) { vector<int> cand={1,1,1}; FORR(e,E[cur]) if(e!=pre&&e<M) cand.push_back(dfs2(e,cur)+1); sort(ALL(cand)); reverse(ALL(cand)); dp1[cur]=cand[0]; dp2[cur]=cand[1]; dp3[cur]=cand[2]; return dp2[cur]; } void dfs3(int cur,int pre,int pv) { int cand[]={dp1[cur],dp2[cur],dp3[cur],pv+1}; sort(cand,cand+4); reverse(cand,cand+4); dp2[cur]=cand[1]; FORR(e,E[cur]) if(e!=pre&&e<M) { if(dp2[e]+1==cand[0]||dp2[e]+1==cand[1]) dfs3(e,cur,cand[2]); else dfs3(e,cur,cand[1]); } } int hoge(int M_) { M=M_; dfs2(0,-1); dfs3(0,-1,0); int ma=0; int i; FOR(i,M) ma=max(ma,dp2[i]); return ma; } void dfs(int L,int R,int retL,int retR) { if(L>=R) return; if(retL==retR) { while(L<R) ret[L++]=retL; return; } int M=(L+R)/2; ret[M]=hoge(M); dfs(L,M,retL,ret[M]); dfs(M+1,R,ret[M],retR); } void solve() { int i,j,k,l,r,x,y; string s; cin>>Q; FOR(i,Q) { cin>>x; E[x-1].push_back(i+1); E[i+1].push_back(x-1); } dfs(2,Q+2,1,17); FOR(i,Q) cout<<ret[i+2]<<" "; cout<<endl; }
まとめ
6問回のボス問にしては複雑でない。