Skip to content

Instantly share code, notes, and snippets.

@n-ari
Last active June 6, 2016 10:52
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save n-ari/d7fae0c486a4099f2d9dc91c3525930f to your computer and use it in GitHub Desktop.
2016 5/30 traPcontest

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#
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment