概要
第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023） の参加記録です。
貪欲解
まずグリッドをBFSしてグラフを得ました。
グラフはDAGになるので、「奥から優先して作物を植える」「植える作物はscore = d-s+1 が大きいものから順に植える」という貪欲をしました。
得点は18,935,125。正の得点が得られたので良しとする。
ビームサーチ解
多様性を持たせるため「1ターンに植える作物の最大個数」「植える作物のscoreの上限値」を変数にして、ビーム幅2とビーム深さ3にしてビームサーチしました。
得点は21,194,750。
これが最終的な提出になりました。
反省点
ビジュアライザを試したらわかるのですが、「1ターンに植える作物の最大個数」を設定しても、1ターン目ですべての区画に作物がほぼほぼ埋まってるので、2ターン目、3ターン目もほぼほぼ埋まっています。なので多様性は確保できず、よくないビームサーチになっていました。
改善点としては、ビームで深さに潜るときに「1ターン進める」ではなくて、「なにか収穫できるまで状態を進める」くらいまですれば状態は変化して多様性は確保できたのかなと思いました。
手元では5000msくらいかかっていても、システムに提出すると時間が1000msだったりするのでそのへん勘所がよくわからなかった。
あと私のビームサーチは遅すぎる。ビットボードや参照カウント方式などの高速化テクをもっと試すべき。
最終的なシステムテストの結果
システムテストの得点：839,674,300
516位
強い人の解法
どうやらグラフの奥まで自由に歩ける「通路」を作ったほうが良いらしい。
#AHC023
— bin (@5bin101) 2023年9月10日
42.4M(暫定18位)
①通路を作る
②通路以外をグループに分ける
③グループごとに、幅12のビームサーチ(1ステップ:DPで1つのマスを決める)をする
④通路もできる限り埋める pic.twitter.com/2pgwYqp7vL
AHC やったこと 暫定 34 位 / 41.5M#asprocon10 #AHC023 pic.twitter.com/JrzqvTyHNg
— iwashi31 (@iwashi31) 2023年9月10日
やってることわかりやすい。
AHC023 暫定22位
— bowwowforeach (@bowwowforeach) 2023年9月10日
入口から木構造を作って、木の葉側からDPで100ターン分のスケジュールを決めてく。オイラーツアーの順序でちょっとずつ収穫する日をずらす。
最後に隙間を埋めたりする山登り。#asprocon10 #AHC023 pic.twitter.com/7juoVzJN0t
暫定33位(41.5Mくらい)です。通路を作ってDPをやっていました。#asprocon10 pic.twitter.com/NmJtxCt6fr
— yunix (@yunix91201367) 2023年9月10日
やはり「通路（道）」と「部屋（葉）」に分けるのが強そう。部屋に何を植えるかは山登りがいけるという方針？
たしかに私のような「通路」を作らない方針だと多様性の確保ができなくてうまくビームできなかったんですよね。逆に言えば「どうすれば多様性が生まれるか」を考えたときに「部屋を作って部屋ごとに多様な状態を作る」というのは思いついてほしかった（自分に）。
AHC023お疲れ様でした 暫定14位だ~~ 嬉しい。
— 玻璃 (@hari64boli64) 2023年9月10日
最小シュタイナー木を擬似的に作ってベースにし、セグ木を使った重み付きスケジューリング問題を解いて局所改善を繰り返す焼き鈍しをしました。
sは最後に決めればいい点や、前計算した関節点で非常に高速な連結性判定が出来る点が面白かったです。 pic.twitter.com/eE48I4MSAX
焼きなましもいけるらしい。全然わからない。焼けるとは思えず完全にビームサーチしか頭になかったです。
感想
AHC、最初は「楽しみ～」→読解中＆貪欲実装中「めんどくさい～」→貪欲後「楽しい～」 という感じでした
