問題ページ まず答えの一番上の行を適当に定める。このとき入力の1~n-1行目までが正しく生成されるように、答えの2~n行目までを定めると一意に定まる。入力のn行目についても正しく生成されるような、一番上の行を探したい。 通りを全列挙することは不可能な…

問題ページ ビットごとに独立 ビットごとの論理和・論理積について考えているため、ビットごとに独立に考えることができる。したがって要素が0か1の の行列を構築できるか？の問題に帰着できた。 容易に決定できる要素 まず、0か1か確定させられる要素を決め…

問題ページ 文字列の長さは についてフィボナッチ数列になっている。したがって については一意に定まる。また、フィボナッチ数列で20000以下となるのは22番目までなので、 である。文字列は高々 個程度しか存在しないので、 を全列挙し、 と一致するか判定…

問題ページ flogに対応する区間を持つ集合・まだ食べられていないmosquitoを保持する集合をそれぞれ保持しておく。 mosquito が現れたとする。このとき を含む区間が存在するか？存在するなら左端が最も小さいものはどれか？を判定したい。内包される区間に…

問題ページ 直線上に多角形の頂点が存在しない場合、直線と辺の交点をに近い方から順番に見ていき、番目と番目の点の距離の和が答えになる。問題は直線上に多角形の頂点が存在する場合で、2つの辺と交わっていると判定されて困る。 点を通過して中に入るパタ…