今日やったこと
今日はAOJ Virtual Arenaを使った練習会に参加しました。
https://onlinejudge.u-aizu.ac.jp/beta/room.html#HCPC2018_017_2
先輩2人とチームを組んで参加しました。
A問題とB問題は眺めている間に先輩が実装をしてくれていました。私はC問題を解きました。ぱっと見て全探索が通りそうなので全探索の実装をしようとしました。先輩のアドバイスによりDFSを3回する実装になりました。ここで、バグが取れずに色々やってなんとかACしました。強い先輩による強力なアドバイスを受け、チーム戦とはこういうものなのか…とか考えました。
今回のバグなど
・変更した配列を元に戻す→判定や処理、の順でやるべきところを、判定→配列を戻すのようにしていた
・引数をfromcolorなどに変更すべきところを0のままにしていた
・4方向を調べる時には、xとyの移動する距離の組をあらかじめ用意しておくと便利
・探索で外側に出ないように周囲1マスずつ余分に確保すると便利(インデックスが混乱すると思い込んでいたけれど使った方がむしろ楽かもしれないので次からは使う)
D問題も読みましたが正直さっぱりだったので、残りの時間は基本問題を2問解きました。
・島はいくつある?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=jp
DFSの練習問題です。8方向を調べる必要がありました。8方向になってもあらかじめ組を用意しておけば手間はあまり増えないので便利です。
・幅優先探索
https://abc007.contest.atcoder.jp/tasks/abc007_3
幅優先探索でした。queueを使いました。queueにpairを追加するときには正しい使い方でmake_pairを使いましょう。queueとpairを組み合わせてコストと座標を記録できるのが便利です。見たマスを行けないように更新するのを忘れないように気を付けよう。
感想
お腹が空くので何か食べてから行くと良さそう。