読者です 読者をやめる 読者になる 読者になる

CF359

解きました.

virtualでA,B,Dの3完でした.

A:ひねりのない簡単なやるだけ.
B:すべての部分木に対して重心を一つ求める問題.
サイズと重心を持ちながら木DP.根が重心になるならOKで,そうでないなら一番大きい子の重心から上げていく.

C:どう考えてもセット内最難関(実際ACも一番少ない).Z^3の点がN個与えられる.min マンハッタン距離(v,given points) (vはZ^3の点) のminをみたすvを一つ出力せよ.
二次元だと45度回転だけど,3次元だと正八面体になるので回転で立方体になったりはしない.しかし必要な値は2^3/2=4で,a=-x+y+z,b=x-y+z,c=x+y-z,a+b+c=x+y+zの4つがある区間にある という条件が各制限になる.同じ形の制限ごとに先にまとめて,あとはちゃんと(x,y,z) in Z^3があるかどうかを判定する.まずちゃんと整数になるというのはa,b,cが同符号 と同値なので,r=0,1に対しa=2a'+rとか置いてa'の条件に変えれば良い.あとはa',b',c'を最小に設定しといて,a'+b'+c'が許す範囲で増やしていけばOK.
細かいところがかなり面倒で,うまいこと同値変形しないとなかなか難しい.細かいところまでちゃんと定式化しようとすることが必要.

D:無限に広がる二次元グリッドのN箇所が黒く塗られている.K*K正方形で中にi箇所ぬられているようなものは何個ありますか(iが正のものは有限)

平面走査*2みたいな感じ.まず縦でいつ追加,削除されるかを持って,処理して,あとは横で処理した分を縦がどのくらいに渡るかの係数をかける.横の処理も平面走査で,一つのマスは高々K回しか処理されないのでO(KNlogN)で出来る.

E:N頂点M辺の無向グラフがある.辺iは時間i以下なら使えて,使うと時間がiに変化する.場所s,時間lから場所tに時間rまでにつけるか というクエリが大量に来るのでYes/Noで答えてください.
N≤1000,M,Q≤200000

O(NM+Q)で出来ます.
最短でaからbにいつつけるかmn[a][b]を後ろから更新していく.辺m=(x,y)が繋がるとき,xからvに行けるならyからvにも行けるようになる(逆も同様) + xからyへ時刻mに着けるようになる.クエリをsでまとめておけば答えられる.

C:Submission #18750874 - Codeforces
D:Submission #18717102 - Codeforces
E:Submission #18732270 - Codeforces