■151F - Enclose All
とりあえず二分探索なのはあきらか。
半径が最小になるときは、少なくとも２つの点が円の円周上にある。
なので二点から距離rの点を中心の候補とし、すべての点が収まるかを確認する。
■152F - Tree and Constraints
制約を見る。NとMが少ない。特にMが少ない。bit全探索をやれと言っている。
制約の部分集合考え、
最低でもこの制約達を満たす場合の数を考え、包除原理をすれば良い。
制約を選択したときにどの辺が使われるかは辺に1<<idを振れば
典型的なlcaとxorで打ち消すパターンになる。
■153F - Silver Fox vs Monster
遅延セグ木。
左から殺していきつつ、区間加算すればよい
■154F - Many Many Paths
パスカルの三角形上での長方形和が求めれればよい
1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
のようなx*yな部分の和はc(x + y,x)-1になる
また
c(6,1)+c(7,2)+c(8,3)+.....c(x,x-5)のような形の和は
c(x+1,x-5) (最後に足したもの左下)になる。
同様に逆にしたときは右下。
証明は帰納法。
■155F - Perils in Parallel
難しい。
区間を変更するときは区間内全てが変わるのではなく、区間と非区間の境目のみ変わる要素を考える
注目すると、そこのみxorが変わるので変わるところ変わるところを結び、グラフとして考えれば良い。
葉から変更していくと、根を除いて自由に変更できるので、最後に残った根に爆弾が残らなければ良い。
類題：典型49
