160530 簡易解説
- A : 書きます。
- B : 剰余を取るといい感じになりそうですね。剰余取って0になった場合がコーナーケース。
- C : 24*60通りしか無いのでboolの配列で持って順にアクセスしてもOK。考えられるパターンが多くなったら配列に入れておいてソートする、set(Java:treeset)といった平衡2分探索木を使う、など。
- D : 始点と訪問する点をすべて含めた際、Cの形(輪っかの一部が切れてる)の様に訪れるのが最適です。輪っかのどこが切れてるかを全探索し、両端へ行くのにかかる時間をd_l,d_rとすれば、その切り方における最適解は
$min(d_l,d_r)*2 + max(d_l,d_r)$ です。 - E : 4通りの遷移、たかだか8回で解ける、ということから、4^8通り全探索です。再帰で書くと良さそう。ちなみに、同じ操作を2連続でやっても意味が無いので3^8通りには落とせますね。
- F : 難問です。私は「(0,0)から(i,j)までにどれだけ*があるか」という配列を累積和を使うことで求めておいて、「各(i,j)から高さh,幅wで行けるかどうか」を探索していきます。ここで、hを最大、wを1として探索を初めて、(i,j)から(i+w,j+h)までの*のある数が0になるまでhを減らし、0になったら答えを更新、wをインクリメントする、という尺取法みたいな方法を使いました。計算量はO((W+H)WH)ぐらい。
- なお、この問題にはO(WH)解法が存在しますが、私はあまり理解していません。以下のリンクを御覧ください。
- http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=496648&tab=2#