Eまで五完。Fはキーワード的には分かっていたのだが……。
E - Rush Hour 2
ダイクストラ法。
$\sqrt{D}$よりtimeが小さいときは、$\sqrt{D}$を調査、そうでなければ普通にtimeのときにかかる時間を計算。
$\sqrt{D}$あたりが極値になりそうなことは、最初は微分しようとしたが面倒くさくなって、
$x+\frac{d}{x+1}=x+1+\frac{d}{x+2}$
を計算した。
これは、$x$が1ずれても同じ値になるところを調べているということ。こういう$x$で極値になるはずなので。
F - Hanjo 2
解説AC。
うーん、行に関する部分集合たちについてDPをして、行列累乗だろうとは思ったし、横2マス見れば現在の状況が扱えることもコンテスト中に考えたはずなのだけど。
しかし、解説をみても、「列iまでみて全ての行ではみだしている場合」と「列i+1までみてはみだしが一つもない場合」は同一のものなのに、DPするとき両方を状態として持たなくてはいけないことにピンと来なかったし、自分にはちょっと分かりにくいDPだったのかもしれない。
遷移の行列を作るところは再帰で書いたけど、これもどう書けば良いか結構迷ってしまった。
0 件のコメント:
コメントを投稿