解いた問題

9/29/2012

LiveArchive5848

分割統治。

領域を縦と横に2分割して、4つの領域に分ける。
縦は2種類の点を分ける様なX軸に垂直な直線で分割し、横はそれっぽい直線で分割する。

横方向に隣合う領域同士の近い点か、斜めの領域同士の点から最近点を探す。
互いに斜めな領域同士の点の移動は、分割に使った縦と横の線の交点を通る様な移動を考える。

あとは、点の数が少なくなるまで横の分割を繰り返す。

9/13/2012

SRM555 Div2 Hard

955

DP1[ n ] = n マス連続して泥でないときの行き方が偶数通りか奇数通りか。
DP2[どこまで見た][泥のマスがいくつか][ 偶数通りの行き方がこれまであったか ]

o を乾いたマス、x を泥のマスとした場合、oooxoooo の行き方は"3マス連続して泥でない道の行き方"×"4マス連続して泥でない道の行き方"になる。
つまり、泥のマスで区切ったそれぞれの連続して泥でない道の行き方の中に偶数通りの行き方のある部分があれば、
全体も偶数通りの行き方が存在することになる(偶x偶=偶、偶x奇=偶、奇x奇=奇)。


前計算で n マス連続して泥でない場合の行き方を計算しておく。
その後、ある2つの泥のマスの間にいくつの乾いたマスを挿入するかというDPを行う。
両端に泥のマスを付け加えるとやりやすかった。

SRM555 Div2 Medium

555

DP[何桁目まで]

SRM555 Div2 Easy

255

やるだけ。