AHC023 参加記 - hogloidのブログ

せっかくなので。

Day1

朝起きて、流石になにか有益なことしたいな…とふと思う。背景としては前の週に喉風邪にかかり、体調は回復してきたのだが外出の予定は全部キャンセルとなり、ひたすらアニメを見るしかしていなかった(面白かったけどね)。自分の中での行動欲メータが溜まってきたのを感じ、ふとatcoder.jp を眺めたらAHCが今日から始まることに気づいた。

前々から実は出たいなと思いつつ、コンテストのためにスケジュールを空けておくみたいなことをしなくなっていたので結果的に一度も出ないままAHC開催から2年以上経ってたんだなぁ。今回ぐらいはなんかの縁だと思って出ることにする。

ただ、最初の目標としては軽く貪欲書いて、C++の書き方思い出して、序盤で上位に着いたらそれで終わりで、残りはまあ適当に流せばいいかな…なんて思っていた。

とりあえず問題を読む。うーむ、なるべく少ないマスを農機が通る用に確保して、残りのマスに置きまくれば楽だろうなぁ。まだ到達してないマスに多く隣接するマスに優先して進んでいって、農機が通るマスの木を構成する。その後は全セル独立に解けるので、置けた時間のスコアを負のコストとして最小費用流として解ける。

最小費用流の負コスト処理、これであってんのかな〜なんて思いながら書く。午後2時。

ウム、よさげ。26M点とか。ちょっとだけ細かい改善をしてみる。

ただこれを提出した頃にすでに自分の1.3倍近いスコアがちらほら出てた。となると、農機のマスの作り方をどんなに工夫しても追いつけない。仕方ないから別の解法を考える。

さっき作った木はそのままに、木の深い頂点から順になるべく育つ期間の長い作物を優先して植えてみる。奥のマスでの収穫にはそこまでの通路すべてで作物が植えられてないことが必要になるので、収穫回数が少ないほうがいい。

まあまあやね(35M)。なんか遠回りさせるより近道の方が通る必要のあるマス減るから、多少通路マスが増えても木は浅いほうがいいよね？とか、細かい改善してみる

38M。1日目としてはこんなもんかな〜と思って終了。

1日目としては久しぶりの実装で色んな実装ミスで引っかかりまくり、これで1週間は大変だな〜と思っていたので、1回でも1位に立ってやめるぞ！(辞めさせてくれ！)と思っていたが、初日から細かい改善するのも疲れるしで、翌日以降に持ち越し。

Day 2-4

木の生成を工夫して、直進的な進み方を優先してみる
- 遠回りしない範疇で、通路マスを少なくできる
作物を植えていく順番は、ノードの深い順ではなく、より大きい部分木を先に取る帰りがけ順に変更
- 小さい部分木の方は制約が少ないので、より難しい大きい部分木の方を先に解くことで、使える作物の選択肢が多く確保できる
収穫できるタイミングのペナルティに傾斜を付ける。例えば子ノードで収穫するタイミングでついでに収穫するのはロスなしでできる。そうでないタイミングについても、兄弟ノードで収穫するタイミングなら新たに犠牲にするノードの数は少ない。新たに制約を作るノードの数に比例するペナルティを付けた

などの改善を入れた。他にもペナルティや優先度周りで細かい改善は試したが、あまり有意な効果はなさそうだった。正直このあたりの貪欲のルールを試す部分は結構好きなのでついやってしまうが、時間あたりの効果は低いんだな〜なんて思ったりした。

40M。10位付近とかそれなりに良い位置にいたのでやる気は出てきたのだが、このあたりでsugim48が突然42Mぐらいで1位に現れる。あまり今の解法の延長になさそうだったので、また1から考え直しか〜と落ち込む。

Day 5-6

悩みまくり。ビジュアライズを見て、迂回できるタイミングなのに木の経路にこだわって空けているパターンは多かったので木のままではだめだろうなと思ったが、グラフに一般化するとノードの間の順序が破壊されて1個ずつ決められなくなってしまい、時間を逆順に見てやるしかなくなりそうだが、実装も大変だしどれぐらい良くなるかにも自信が持てなかった。DAGに一般化することについても、順序は決まるのである頂点での収穫のタイミングを複数の経路に分散できるのは分かったが、効果が限定的なような気がして実装する気にならなかった。

ふとマスが一直線のケースを考えてみようと思った。あるマスであるタイミングで収穫するということは、それより手前のマスでそのタイミングをまたぐ作物は植えられないということで、マスの数×時間の2次元のグリッド上に、交差できない線分があり、作物に対応する1×(D-S) の短冊をたくさん置いていく問題だな〜と思う。これは(交差できない線分=各マスの収穫のタイミングが決まっていれば)貪欲で厳密に解ける。実際はこれが木やグラフに一般化されているが、貪欲で解ける点は同じ。

最初本当にうまくいくか自信なしだったのでアイデアとして置いていたが、他があまりにも筋悪そうだったのでこちらを試してみることに。また実装やり直しで落ち込む。

まずは木ベースで、収穫のタイミングを適当に選んで根から通るマスを決めていく。単に最もスコアが増加するパスを選ぶだけ。これをスコアが増加する間繰り返す。それなりによくなった、が最上位には届かないぐらい。タイミングを選ぶ順番、貪欲にパスを選ぶときのスコアに若干の調節を入れる、いろんなのを試したが効果は少なく、もうこれは貪欲でどうこうなるものじゃなく焼きなまししかないかな〜と思い始める。

42.2M

あとこの時期あまりよく眠れなかった。普段から朝方にうとうとするタイミングはあるがすぐ意識を失うんだけど、うとうとした瞬間問題のことを考えだして目が冴えてしまうため。長期コンって大変だぁ

Day7

木ベースのまま焼きなましを書く。状態は、{t_i, {v{i, j}}} := 時刻 t_i について、根から頂点v{i, j} へ収穫しに行く。近傍は収穫しに行く頂点の削除と、今既に収穫しに行くノードから最大5深い頂点を追加する。

43M 弱ぐらい。思ったより伸びないな…と思い、近傍に傾斜付けたり、初期値もっと頑張ってみたりしたが、良さそうと思ったアイデアが尽くダメでかなり無力感があった。2M上げるには、なんと毎時刻16個も多く埋めないといけない！今明らかに植えられていないがガッツリ緑になっても足りない。流石に木のままではダメだろうなと思い、木にこだわらず連結な経路取れるように変更することを決意するが、その場合初期値はこれでいいのか？というのがかなり気がかりだった。初期値で明らかに木に最適化した形をしているので、ちょっと経路変えてもスコアは上がらないんじゃないかと心配していた。

ただ、残り時間的に初期値と焼きなましの両方を改善するのは厳しそうだったので、まずは焼きなましの部分だけをグラフに一般化することにした。またも実装した内容が無駄になり、涙……。

とりあえず状態は各時刻の根から連結な頂点集合で、近傍は関節点以外をランダムに消すのと、隣接する頂点からランダムに追加するだけ。 day7中に実装は終わる。試行回数上げてなかったけど 43Mそこそこぐらいはあったかな。

合計スコアもさることながら、今まで通路専用だと思っていたところでも平気でスコアを稼いでくるのが驚きだった。確かにこれ見るだけでもだいぶ情報量あるよね。

Day8

通路を崩すことが大事っぽいので、それを誘発するように近傍を作ってみるが、あまり効果はなさそうだった…。初期値も工夫したかったが、焼き鈍しの試行回数を増やせば思ったよりもうまく初期値と違うところに到達できていたので、残り時間がないこともあってやめた。焼き鈍し回数を10倍にすれば(今の順位表で)1位行ける！というのは分かっていたので、とにかく高速化を頑張ることにする。初めてプロファイラを使った。gprofというのが標準的らしいので使ってみる。-O2を付けるとたまに関数がインライン化されて消えてしまうが、O2付けないプログラムで測ってもしょうがないので諦めてその情報でボトルネックを探す。関節点の判定を毎回やるのは無駄で、更新があったときだけとか、近傍全列挙は無駄で、グラフをビットで持って個数を最初に数えて何番目かを決めてから取りに行く、1つの頂点だけに隣接して追加するときは繋がれた側が関節点になって他の頂点は変化しないから再計算不要とか。あと初日にコード書くのサボってサンプルのグラフの持ち方のままだったので関節点の所だけは4方向の辺ありなしをビットにまとめたりもした。

スコアの変化も、どうせO(T)はかかるものの定数倍速そうな方針に変えた。

割と一通りやりたいことはやれたな〜と思ったタイミングで提出する。温度調節とか、時間計測を書きながらスコアを上げていく。

44.7M！出した瞬間は1位になった気がするが、すぐsugim48に抜かされてしまった。0.3%程度の差だったけど、10% 高速化とかでは逆転しなさそうな差だったので残念だった。追い上げに備えて多少の高速化を図りつつ終了。

1位行けるかも！と思っていた終盤4時間とかはめちゃドキドキしていた。疲れはするけどこういう興奮もたまにはいいね。

振り返ると自分の場合は正しい解法にたどり着くまでに相当な紆余曲折があったので、最初にもっと問題の構造を考えても良かったな〜と思った。まあでもたくさん実装してたくさんデバッグできたのは良かったかな、昔だったら単純作業と思ったかもだけど最近C++書いてなかったので。あと小手先の改善や小手先の高速化繰り返すのは実は結構好きなのも分かった。

1週間は思ったより長くて、早く解放してくれ〜って思うタイミングは何度もあったが、一番自分に有利なタイミングで終わってくれたので文句は言えまい。

終了後は久々に解法ツイートっぽいのをしたり、他の人のビジュアライズ見たりしてた。ヒューリスティックは知らない人多くて、懇親会も楽しみ。