問題 解法1 クエリ平方分割 もしクエリが1つしかない場合、以下の方法で求められる。 森の連結成分ごとに適当に根を取り、DFSで各頂点の親を求めると、各クエリについて、 と の親のいずれかが候補になるため、親を とすると、辺 と辺 が存在するかを、辺集…

問題 解法 適当に の領域を3つの長方形に区切り、さらにそれぞれの長方形から の正方形を取り出すと考えて良い。 その場合、3つの長方形の区切り方は以下の6つのいずれかになる。 |--------| |--------| | | | | | | |--------| | | | | | | | | | | |------…

問題のリンク 解法1（LowLink） LowLinkのアルゴリズムをベースに少し改良を行い実装する。 ところで、LowLinkを改良するアルゴリズムを考えるときには、（実際にはまとめて行っているが）まずDFS Treeをとり、そのDFS Tree上にある辺かそうでない辺（後退辺…

問題のリンク 解法 線形代数の授業でやるような掃き出し法を、 行 列の行列で、左側を上位ビットとみなすイメージでやる。 すると、総XORで作れる要素を昇順に並べたときに 番目に来るような要素について、 の ビット目が経っている場合、基底の（2進数で見…

問題のリンク 遅すぎるかも。 解法 シートA, Bは少なくとも1つ以上の黒いマスを含み、そのマスは必ずシートXのいずれかの黒いマスに対応する。 よって、それぞれのシートから1マスずつ選び、シートXのどのマスに対応するかを全探索し、シートXのそれぞれの黒…

解けたのでおまけがメイン。 問題のリンク 概要 与えられた単純無向グラフについて、辺を 本以上取り除くことでいくつかの完全グラフに分割するときの、完全グラフの個数の最小値を求めよ。 解説 個の頂点集合を順に列挙し、それぞれの頂点集合に対し、その…