Dまで遅解き四完。実装要素の多いコンテストだったから、あまり順位が良くなくてもまあ仕方なかったかな、という気持ち。
C. Fillomino 2
できるだけ左に、下に～と、端から詰めていけば良かったらしい。
「どれかの数字では三方に進めないため次に進む一方向が定まる」という状況が続くので、それを利用してDFSみたいにしてしまったけど、もっと単純な解法がないか疑うべきだったか。
D. Explorer Space
こういう問題はn=mにして欲しい。毎回、縦と横で混乱してしまう……。
E. Group Photo
条件全てが満たされる場合ってあんまり多くなさそうだよね、という直感に従って場合分けしていく問題。
Cの位置で場合分けすると、
・右端に何個かC
・左端に何個かCが続いた後、一個置きにCが現れる（最後はP）
・左端に何個かCが続いた後、一個置きにCが現れ、最後もC
・一番左端はP。二個目から何個かCが続いた後、一個置きにCが現れる（最後はP）
・一番左端はP。二個目から何個かCが続いた後、一個置きにCが現れ、最後もC
という感じになり、これは、累積和と、一個おきの累積和を持ち、尺取り法を使えば求められる。
ただ、一個おきの累積和を使うため、この上さらに、一個起きのindexが偶数か奇数かで場合分けをしなくてはならず大変だった。
ちょっと書き方が悪い部分はあったけど、コンテスト中に間に合わなかったのも仕方ないかなぁ。
0 件のコメント:
コメントを投稿