C - 広告 概要 R × Cマスのグリッドが与えられる。グリッドは . か * で構成される。 . のマスに広告を配置させることを考える。ただし、広告は他の広告と上下左右で隣接しないように配置したい。 配置できる広告の最大値を求めよ。 制約 1 ≦ R, C ≦ 40 方針…

F - Must Be Rectangular! 概要 2次元平面上にN個の点がプロットしてある。i番目の点の座標は(x[i], y[i])と表される。以下の操作を可能な限り繰り返す。 次のような任意の4か所(a, c), (a, d), (b, c) , (b, d)のうち、ちょうど3か所に点がプロットしてある…

Problem - D - Codeforces 概要 整数集合Bが与えられる。1から始まる全ての整数をグラフの頂点と考え、|i - j| ∊ B であれば、iとjに辺を結んでいく。 このときできるグラフを2部グラフをするために、Bから要素を消去することを考える。消去すべきBの要素の…

CODE FESTIVAL 2017 qualB C - 3 Steps(500) C - 3 Steps 概要 N頂点M辺の連結無向グラフに、「長さがちょうど3の経路をもつ2頂点間に辺を追加する」ということを繰り返す。追加できる辺の最大値を答えよ。 制約 2 ≦ N, M ≦ 10^5 方針 最終的に、奇数長の経…