1.はじめに
AHC022に続いての長期コンテストということもあり、前回の学びを書きます
・思いついた解法は必ずメモして、試す
・変数のサイズによって解法の不得手が無いか考えてみる
・根拠の無いパラメータ調整に時間を割かない
平日は仕事もあり、中々時間を作れないため日中にアイデアを溜めて、夜に色々試すしかない。というのもありました
2.問題
H×Wの土地(20*20)に、Tカ月(100カ月)でK種類の作物を育てる問題でした
土地には水路があり通れないことや、栽培中の作物の上も通ることができない。という制約がありました
また、植える月と収穫する月が作物毎に決まっており、植える月だけは先出ししても良いとのことでした
3.初日の取り組み
・常に空けておく通路を作って、アクセスできる区画に作物を詰め込む
・同じ経路でも月によって通れる通れないがあるため、H*W*Tの3次元で考える
そうして出来た、初提出のビジュアライズがこちら
やりたい事は一旦できていることが確認できました
次に考えた方針としては
・入口から遠いほど作物を置きにくい→奥から決めていく
・最後の月に必ずまとめて収穫できることから、収穫日が遅く、植える日が早い作物から決めていく
・植える場所を決めたら、入口までの最短経路に[植える月]と[収穫する月]をメモして、後から植える作物がそれを邪魔しないようにする
一気にそれらしくなりましたね
ちなみに、この提出はコンテスト開始約4時間のタイミングで、なんと順位表で5位になり、かなりテンションがあがりました
暫定5位なんだけど、えぐ！ pic.twitter.com/E4F9Hqmb5M
— uta_ccc (@uta_cccc) 2023年9月3日
ちなみに、通れる通れないのメモの仕方として、H*Wの1次元配列にビット列でメモをしていました。どういうことかと言うと、
植える日=1月目、収穫する日=3月目の作物を植える際は、
植えた区画には 0b0010 と記録
通路の区画には、 0b0101 と記録しておくことでビット列で月日を表現できます
Pythonには整数の上限が無いので、2^99も問題ないようでした
(あまりに大きいと速度が落ちるなどあるのでしょうか？
4.2日目以降
正直、最初の方向性以上に得点ができる考えが見つからず、ただ改良を重ねる日々が続きました
幸い、アイデアだけは浮かんでいたので色々試した過程を紹介しようと思います
・通路に使う区画の優先度を決める
先のビジュアライズで2マス幅の通路があるのが気になったため、通路があるにしろ1マスにしたいなという思いから、最短経路のうち優先度の高い区画を選ぶようにしました
優先度の付け方は、これまでに通路として使われた回数。を使いました
後に植える作物は、以前に植えた作物と同じ道を通りやすくなる。という算段です
明らかに通路の幅が狭まり、スコアも一気に上がりました
この時、同時に採用したアイデアとして植える月に通る経路と収穫の月に通る経路を別々に探索する。というものでした(こっちの方が寄与度大きいかも
ただ、区画に植えてある作物の変数と、区画毎の植える月を把握する変数と、区画毎の収穫する月を把握する変数と、などなど管理する変数が一気に増えたせいでバグさせまくりながらなんとか実装しきりました...
・先に通路に使う優先度を計算しておく
これは、作物を植え始めてから優先度を決めるのではなく、先にある程度優先度を決めておいて、それに加えて作物を決定しながら優先度を上げていくようにしました
上は、エクセルで可視化したもので、なんとなく壁から離れたところを通らせようとしているのは伝わるかなと思います
各区画について、上下左右の壁との距離*2+2の計算をしているだけです(+2はお気持ち程度
また、植える区画を検討する順番についても、入口からの最短距離+周囲の壁の数 を採用して、壁周辺から作物を決めていくようにしました
この時点で、3日目(9/5(火) でしたが、このまま進んでも40Mまで届かないな？とは思っていました
別解法として、
・植える毎に全時間の最短経路を計算し直して、回り道も含めた経路を見つける
・作物毎に区画を探索するのではなく、区画毎に作物を詰めていく
など考えて実装までしましたが、あまり得点は出ませんでした
それでも、探索順にランダム性を持たせて、最も高いスコアを採用する(乱択貪欲？)や、少しでもループ数を稼ぐために処理を軽くしたりして、最終的に39Mのスコアまで何とか出すことが出来ました
5.終わりに
システス後の順位は、135位と自分にしては頑張ったほうかなと思います
平日もAM2時くらいまで粘って寝坊しかけたりしましたが、それだけこの1週間のめりこむことが出来ていたのかなと
また今回の結果で、水色に入ることが出来たので結果としては大満足です！
終わってから、一気にみんなの解法がTLに流れてくるのも面白かったですね
最上位の方は焼きなましに持って行けていたり、通路で区切ってdpで最適化など、この1週間で全く考えもつかなかった内容が多くありました
次のAHCまでに、概念だけでも理解したいですね
同じく取り組んだ方々、お疲れさまでした！
