2012-04-16から1日間の記事一覧
問題概要 (sx,0)から(gx,N) (N 解法 愚直に可視グラフ作ってからDPするのはO(N^3)。少し工夫を加えるとO(N^2)まではすぐに落ちる。 想定解っぽいのは適宜メモ化しながら下から順に計算するらしい。 自分は左側と右側の壁で交互に凸包つくって、凸包の頂点は…
問題概要 一部が埋められた8クイーンがあるので残りを埋めて出力する問題。 解法 5!+枝刈りとかでもよいのだけど、以前書いたN-Queenソルバ(全生成)があるのでそれを使って8-Queenの盤面全部出して与えられたのと合致するかだけ調べた。
問題概要 幅優先探索で距離を求める問題。