Educational Codeforces Round 44

スポンサーリンク

A. Chess Placing

ソートして 1, 3, 5, … または 2, 4, 6, … と対応.

B. Switches and Lamps

各列の個数を持っておくと1行捨てたときの判定ができます.

C. Liebig’s Barrels

最小の v は確定し,選べる範囲は確定です.あとはソートして $K-1$ 個以下しか飛ばさないような範囲でなるべく大きいものを選んでいきます.

D. Sand Fortress

$n$ を決めたときの上限は山型の bitonic な列で,上限以下はすべてできるので二分探索が可能です.

E. Pencils and Boxes

ソートして dp.ある境界に対する判定は,ある区間 ($k$ 個以上になる,差が $d$ 以下になる)に前回の境界がとれるかです.

F. Isomorphic Strings

26 個の rolling hash が等しいかという比較でできます.

G. Team Players

辺 $ij, jk, ik$ がそれぞれ conflict しているかという包除原理を考えます.すべて conflict というのは三角形列挙(https://judge.yosupo.jp/problem/enumerate_triangles)でできます.他はひとつの辺または頂点のまわりで算数.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました