2020/5/11

第2回PAST G

一つずつ削除、追加をすると間に合わない

操作区間の長さに対して、区間内の要素の種類数が十分少なくなるような操作

→ランレングス圧縮

 

第2回PAST H

グリッド上を愚直に探索しては間に合わない

興味のある経路はS,1,2,...9,Gをこの順に通る経路のみ

→1-9の各マスに対して、S-1,1-2,...9-8-9,9-Gの間に辺を貼ったグラフでダイクストラをする(必要な辺だけを抜き出して考える)

辺の数は高々10*NMなので間に合う

 

第2回PAST L

ある要素を選ぶことができるかどうかは後ろの残り個数に依存

→後ろから、この位置までにいくつ選ぶ必要があるのかを前計算しておく

後は前から見て、取る必要のある位置で、その位置より前の最も良い数をとっていけばよい

最も大きい値の取得と、その値より前の位置にある削除がしたい→set

 

第2回PAST M

周期性がある→ダブリング

丁寧丁寧丁寧丁寧にえいえいえいえいえいえいえい

 

第2回PAST N

平面上の数え上げ→平面走査

x座標昇順に見ることを考えると、区間addと一点取得ができればよい

→遅延セグ木でえい

 

第2回PAST O

いつもの

クラスカル法でMSTを構成する際、追加する辺のコストは単調増加

→並列二分探索で、ある頂点間のパス上で最後にMSTに追加された辺がどれかを特定する

 

ダブリングでも解ける

各頂点について、根の方向に2^i回進むときの途中の最重辺を求めておき、lcaを利用して各クエリごとにlogNで調べる