はじめに
AHC023に参加したので何をやったのかを書いていこうと思います。文章を書くのが絶望的に下手なので早速始めようと思います。
注意：これは自分がやったことのメモ程度のものなので、それを読みたい物好き(？)の人だけ読んでください
問題の概要
H*Wのグリッドの土地があり、K種類の作物を育てたい。各作物には収穫する月が決まっており、植えていなければいけない月も決まっている(それより前に植えても構わない)。植える時と収穫するときには出入り口から耕地まで水路を跨がず、作物が植えてある耕地を通らずに移動できる必要がある。出来るだけ多くの作物を植えたい。
やったこと
9/6(4日目)
問題文を読む。思ったよりシンプルだけど焼きなましが刺さらなさそうだったので貪欲ベースでいこうと思う。この時点で「作物をSi以前に植えるメリットなくね？」と思ってしまう。これが全ての過ちの元凶だった。
直感的には奥から詰めていけば効率よく植えれそうな気がする(stackのイメージ)。
とりあえずグリッドをそのまま使うと水路の判定が面倒そうだったのでグラフにする。
9/7(5日目)
とりあえず全マスを「道」と「耕地」に分けようとする。
出入り口のあるマスを始点にBFSをし、遠い順に「耕地か道かが決まっていなければ耕地にし、入口までの道を作る(道と繋がるor入口に着くまで)」を繰り返す。
9/8(6日目)
とりあえず耕地にしたところ(行き止まりを想定)にDiが遅い順に詰めていき、提出。得点は13051050点で456位。上位の人たちが35Mあたりで戦っていたので20Mを目標にしようと思う。
9/9(7日目)
昨日の提出をもとに、植えていない作物を選び、耕地(行き止まり)の手前のマスに植えられるかどうかを判定、植えられるなら植える、を繰り返す。これをビジュアライザで確認したところ、「道に植えたせいで別のところから収穫できなくなる」ところがあることが分かる。「どうしようかな……」と思いながら一日が終わる。
9/10(8日目、最終日)
この時点で500位/750人くらいになっており、焦る。
植えた時点で出入口までを最短距離まで辿り、SiとDiを予約することでgot a kotonaki……と思いきやなぜか収穫できないことがあり、頭を抱える。追加植え付けの回数を手動で決めるという苦肉の策も、ほぼ上がらず13066100点、システス537754225点で580位。
反省
・作物をSi以前に植えるメリットを思いつけなかった(これがとても本当に一番重要)
・手元で実行してファイルにする環境がなく、コードテストで実行していたので慣れていなかった(これ手元でどうやるか知ってる人いたら教えてください)
・普段通りの生活をしていたため、あまり時間を取れなかった(AHCはどんな活動にも優先されるべきです)
