HACK TO THE FUTURE 2020予選 参加記

コンテストページ

https://atcoder.jp/contests/future-contest-2020-qual/tasks/future_contest_2020_qual_a

シミュレータ

手法

• ゴールからBFS。ブロック以外の全マスに方向マスを置く
• 人の動きをシミュレートし、踏まれない方向マスを削除
• →→→などのマスはまだ削れるので、各方向マスから上下左右に、別の方向マス(or ブロック)にぶつかるまで見て、依存されていなければ消す

結果

• これで490万点
• 316位。ギフト券圏内だったけれど当たらず
• ここで終了
• 解説放送を見ると、ゴールから方向マスをつないだツリー構造になっていることに気づくことが重要そう
• ツリーになるとそれの繋ぎ変えができて、外したり繋いだりして評価することができ、マラソンっぽくなってくる

BFS2

• 私は上下左右1マスを見たBFSをしたが、最短距離を歩く必要はない
• 上下左右の、ブロックにぶつかるまで伸ばすBFSをした方がよかった

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?