Codeforces Round 257

2014-07-20 | [Competitive programming]

A

H * W のグリッドに，グリッドを横切りかつマスを破壊しないような K 本の線を引く． 線によって分かれる部分のうち面積最小のものの面積を最大化せよ．

縦方向に切る回数をだいたい全部調べる． ただし，1 回増やしても縦方向の長さの最小値が減らないようなときには 1 回増やしてかまわないので，うまくさぼる． すると O(H) とか O(K) とか調べなくてもすむ．

B

連結な無向グラフがある．グラフには道路の辺と鉄道の辺（頂点 1 とそれ以外の点を結ぶ）がある． 頂点 1 から他の点までの最短経路長を変えないとき，鉄道の辺は最大で何本消せるか．

鉄道の辺のコストに +ε して Dijkstra を行う． Dijkstra 中に鉄道の辺を見た時，行き先が visited であることとその辺を消してよいことは同値．

C

1～N の数から，できるだけ多くのペアを作れ．ペアの 2 つの数の GCD は 2 以上でなければならない．

2～N の数をそれぞれ「その素因数のどれかに対応する箱」に入れ，基本的には同じ箱の中でペアを作る．とりあえず最小の素因数の箱に入れる． p >= 3 について，箱 p の中に奇数個しか入っていない場合は損をするので，箱 2 から数 2p を横取りしてくる． ただし 2p > N のときは，p はそもそもペアに関与できないので無視する．

D

整数列から 1 個以上選んできて，AND が 0 になるようにする方法は何通りか．

包除原理

E

NM のグリッドの格子点を特別な点とよぶ． よい正方形を，頂点がすべて特別な点である正方形で，大きさが 11 のものとする． 頂点がすべて特別な点である正方形（斜めになっていてもよい）すべてに対して，次を行う： 「その正方形に含まれるすべてのよい正方形の中に，石を置く」 最終的に置かれる石の数を求めよ．ただし 100000 個くらいの N, M の組に対して解答しないといけない．

答えを総和の形で書いて，前処理でがんばってそれをクエリ O(1) で計算できるようにする．

結果

全部通った．5560 点 (1 位)

rating: 1947 -> 2188 (+241)