CF AIM Tech Round 3 (Div. 1) (708) - sigma425のブログ

A:場合分けはじめのaじゃないとこからaじゃないとこまでだけどaaa->aazに注意
B:場合分け 0がない時と1がない時とそれ以外で,それ以外だと0と1の数がわかるので全体と合ってることを確認した後は適切に0001111からずらす(計算して).
C:全方向木DP.dp[v]=v以下でN/2以下のサイズの部分木の内でもっとも大きい物をもつとvをcentroidにしたければvの子uのうちN/2よりでかいものからできるだけでかく(つまりdp[u])を切り取ってvとつなげばいいのでこれはdpを計算すればわかるあとは全方向にすれば終わり.
コンテスト後にすぬけが言ってたように,そもそも重心を根として木DPすれば,切るのは重心をまたいだ部分なので楽に実装できるっぽい.
D:min_cost_flow.
元々a->bにf流れていてmaxがcっていうのを,

		if(f<=c){
			sum+=f;
			add_edge(a,T,f,0);
			add_edge(S,b,f,0);
			add_edge(b,a,f,1);
			add_edge(a,b,c-f,1);
			add_edge(a,b,INF,2);
		}else{
			ans+=f-c;
			sum+=c;
			add_edge(a,T,c,0);
			add_edge(S,b,c,0);
			add_edge(b,a,c,1);
			add_edge(a,b,f-c,0);
			add_edge(a,b,INF,2);
		}

こうする.(add_edgeはfrom,to,capacity,cost)
SとTっていう新たな頂点を追加して,

f≤c の時

すでにf流してあるというのは, a->TとS->bにf流さなければいけないという設定にして,f* ≤ f の時, (fを減らす) コスト1でb->aに流し戻せる(ただしfまで)
f* > f の時, (fを増やす) cまで(つまり新たなグラフでc-fまで)はコスト1で増やせて,それ以降はfとcを共に増やす必要が有るためコスト2になる.

f>c の時

まず絶対にf-cのコストは掛かるため,これを答えに足しあわせておく.そして今c流してるという設定にしておく.前述のf-cのコストの範囲で,c流す~f流すまでは自由にできる(cを減らし,fを増やすことで)ので,f-c分はコスト0で流せる.さらに追加分はコスト2.fを減らすのはコスト1でcまで減らせる.
sumでS->Tに流さねばならない分を計算していて,これでS->Tにsum流す必要があって,それとは別に0からN-1に自由に流して良くて,これはN-1から0へ辺を貼ればOK.その後min_cost_flow(S,T,sum)を呼べばおわり.

E:dp[i][l][r]=i段目が[l,r]でまだ連結な期待値みたいなのを持つと更新をうまくやればO(W^2 * H)でできる.更新をうまくやるのにlsum[i][l]=sigma dp[i][x][l] みたいなのを持つんだけど,実はdpはいらずにlsum,rsumだけ持って更新ができて,この更新もO(1)でできるためO(HW)になり終了っぽいけど面倒だし実装してない.

コンテスト:
C開いたらモロ全方向木DPで笑ってしまった(ついこないだ書いたばっかり) やる→Bで1WA→Aやる→E考える→順位表見る→Dが結構通されている→D通すみたいな感じだった.
Bが落ちてキレた.

A:Submission #20123051 - Codeforces
B:Submission #20134838 - Codeforces
C:Submission #20116938 - Codeforces
D:Submission #20131523 - Codeforces