📑

AHC023(第10回Asprovaプログラミングコンテスト)参加記

2023/09/12に公開

ヒューリスティック

ahc

tech

はじめに

第10回Asprovaプログラミングコンテスト(AHC023)に参加しました。
926人参加でプレテスト150位、最終145位で成績・解法とも特筆すべきものはありませんが、間口を広げることを狙います。

問題

問題文はこちら

$20\times20$ 区画の土地に $100$ ヶ月で作物をできるだけ沢山育てる
1ヶ月は前半と後半に分かれており、前半で作物を植えて後半で作物を収穫する
作物 $k$ は $S_k$ 月までに植え $D_k$ 月ちょうどに収穫する必要があり、スコア $D_k-S_k+1$ を得られる
各区画は4近傍に移動することができるが、水路をまたぐ移動と栽培中の区画への移動は不可
同じ月に植える作物、同じ月に収穫する作物の順番は、明示しなくてもよい

前後半に分かれているところは誤読していた人もちらほら見えました

印象

ある区画-作物の割り当てが他の区画-作物の割り当てに影響するから、一部分だけ変えるのが難しく単純には焼きなませない
-- そういう焼きなましの記事があったはず $\rightarrow$ これとか
「区画 $(i,j)$ に作物 $k$ を植えられるか」を愚直に判定すると $D_k-S_k+1$ ヶ月 $\times HW$ マスのBFSが必要になり、とてもやっていられない
-- 何らかの制約を付けて判定を楽にしたい
入力生成方法の $L=\bold{round}(HWT\times\bold{rand}(1.0,2.0))$ を見ると、全ての作物を植えることはできない
-- Lが大きいと難しい? $\rightarrow$ いや、Lが大きい方が作物の選択肢が多いから簡単
植える方のタイミングだけは1~ $S_k$ 月まで洗濯の余地がある $\rightarrow$ これが逆に面倒臭い

方針1: 通路用の区画と作付用の区画を完全に分ける

割り当てが相互に依存するのは面倒なので、手始めにと考えたのがこれです。

通路用の区画は出入口と連結で、作物を一切植えない
作付用の区画は通路用の区画と1辺以上で隣接する

ようにすると、作付用の区画で何をやろうと他の区画に影響しないのでとても見通しが良いです。では、そのような通路用-作付用の分類はどのように実現できるでしょうか?

真面目に考えるとそれだけで時間を取りそうなので、作付用の区画をなるべく多く取るような貪欲を考えました。

まず全区画を「接触不可能な区画」として初期化し、出入口を始点にBFSしながら「通路」を広げます。「通路」に隣接し、「通路」でない区画は「通路に接する区画」とします。
「通路に接する区画」から新たに「通路」を伸ばしていって「接触不可能な区画」が無くなれば終了ですが、その時に 「通路に接する区画」をなるべく多くしたいです。

このお気持ちを貪欲にすると「通路に接する区画」のうち「通路」にすることによって「接触不可能な区画」が最も減少するものを選ぶ、となります。

これを実装するには「通路に接する区画」が何か所の「接触不可能な区画」に接しているかを保持しておき、その数の順で優先度付きキューを使って辿ると良いです。

その結果がこちらです。

9月5日(コンテスト3日目)お昼に初提出して150位・実行時間4msと、伸び代を存分に残しつつまずまずの位置に付け、今後の改善に期待が高まりました。

方針2: 出入口を根とする木を作り、葉から順に計画する

作物を植えられるか否かの判断

方針1を起点に考えると作付用の区画を邪魔しないよう通路にも植えたいとなります。幸い、方針1の実装時にBFSで作付用の区画を葉とする木構造を作っていました。
邪魔をしないとは、注目している区画の部分木に属する区画で作物を植える月と収穫する月には栽培しないということです。

部分木を扱う典型といえば木DPです。木DPで良い感じに処理できないかと時間を使って悩みましたが、作物 $k$ は $S_k$ 月までに植える必要がある $\rightarrow$ 作物が決まっていても実際植える月は確定していないという性質をうまく扱えずに断念しました(植える月を何らかの法則で決め打ちすれば出来ますが、それが後々足枷になるのではという疑念が拭えませんでした)。
その代わりに、計算量には目を瞑って部分木に属する区画・栽培する作物全てをチェックしました。

しかし何ということでしょう。今、書きながら気付いてしまいました。

もう一度先ほどの図をご覧ください。

赤枠で囲った部分に注目すると、植えられる期間を全て覆ってしまう計画は直前の収穫月をも覆ってしまうことが分かります。従って植えられる期間は見る必要がなく、収穫月を覆っているかを確認すれば十分です。

収穫月は一意に定まるので、覆ってはいけない月の集合を管理すれば部分木に属する区画全てを見る必要はありません。 $T$ =100なので覆ってはいけない月をbitsetで表せばマージも楽にできます(bitsetを使う工夫は最初からやっていました)。

植える作物の選び方

上記のような勘違いと、部分木に属する区画の列挙をミスって多重カウントしていたことから無駄に処理が重くなり、この方針に取り組み始めた当初は1区画あたり数百個の作物しかチェックすることが出来ませんでした。
選び方の工夫でスコアは上下しそうですが、ひとまずのベースラインとして乱択することにしました。作物をランダムに選び、植えられるなら植えるという方針です。とりあえず1区画500個で提出したところ31Mになりました。

その後、時系列は前後しますが部分木に属する区画を多重カウントしていたことに気付き、それを取り除いたところ余裕で全作物をチェックできるようになりました。そうなると「植えられるなら植える」という方針はいかにも筋が悪く、何らかの意味で一番良い選び方をしたくなります。
作物ごとにスコアと植えられる月と収穫する月が決まっており、植えるor植えないを決めて総スコアを最大化したい…

はい、これは定番のナップザックDPそのものですね。

$dp[t]$ を $t$ 月以前に収穫する作物を使って得られるスコアの最大値とすると、 $dp[t]=dp[t-1]$ で初期化したあと収穫月が $t$ であるような全ての作物 $i$ に対して $dp[t]=\bold{max}(dp[t],dp[S_i-1]+D_i-S_i+1)$ をすれば更新できます。

ただし、生のスコアをそのまま使うと栽培期間が短い作物を使って隙間を埋める選び方が現れやすくなると予想されます。奥から手前に詰めていくことを考えると、栽培期間が長い作物を優先して使ってほしくなります。
そのお気持ちを反映すべく、生のスコア $V_i=D_i-S_i+1$ を多少いじって $V_i-1$ を使いました。だいたいこの辺の工夫が入った途中経過が以下です。ほぼ最終版に近い点数になりました。

ちなみに、上のコードから $-1$ をやめて再提出したらこうなりました。お気持ちを馬鹿にしてはいけない。

なお最終版ではここも調整して $2V_i-3$ を使いました。雀の涙くらい変わります。

改善1: ある区画~出入口までのパスを再計画する

今回の方針は、どの区画から栽培計画を決めるかという順番に依存して結果が変わります。なので、順番を入れ替えて作り直す作業を繰り返せば偶然当たりを引くことが期待できます。
木を全部作り直すか部分的に作り直すかについては、試行回数がボトルネックと考えていたので後者を選びました。
ある1つの区画を変更するとその区画から出入口までのパス上の区画全てが影響を受けることから、

ランダムに区画 $i$ を選ぶ
区画 $i$ から出入口 $e$ までの、 $i\rightarrow e$ パス上の区画に割り当ててある作物を全て解放する
区画 $i$ から出入口 $e$ まで計画をやり直す
1に戻る

という具合です。パスを1つ作り直しても同じ選択が最適になる可能性が高いので、複数選ぶようなやり方が良かったように思いますが、手が回りませんでした。

この工夫はかなり早い段階から入れており当初はそれなりに効果がありましたが、ベースが改善されていくに従って効果が目減りして最終的に38.7Mを38.75Mにする程度の寄与になりました。

改善2: 木の迂回路がある区画を探す

ここまで、区画間の移動は全て予め決めた木の上で行うものとして割り当てを考えていました。このような移動方法では部分木の区画の栽培計画を邪魔してしまうような場合でも、迂回路を辿って出入口に到達できるなら作物を追加することができそうです。
では、そのような区画はどうやって見つければ良いでしょうか?ABC319をサボって考えた結果、以下のような区画に栽培しようとしてはいけないと判断しました。

出入口
その瞬間に到達できない
植えるor収穫するために到達しないといけない区画の、唯一の接点になっている
木にする前の、元のグラフにおいて関節点になっている

絵にするとこんな感じです。

ここで2つの候補を描いていますが当然2つ同時に塞ぐことはできないので、1つ選ぶごとに再計算が必要です。同じような候補を一旦全ての $t$ について求めて時間方向に並べたとき、最も長い区間だ取れる候補を選び、植えられる作物がないか探しました。
もう少し工夫の仕方もあったような気はしますが最終日で時間もなかったので、とりあえず動くところまでやって終了しました。

関節点を求める手法としてLowLinkが知られていますが、自分で実装する余裕がなかったのでLuzhiled's memoから頂きました。ありがとうございました。

効果は38.75Mが38.77Mになる程度のものです。

結果

アニメーションGIFを張ろうとしたら3MBまでということで弾かれました。
最初の絵からはかなり進歩したと思います。

スコアの大半は「BFSで木を作ってナップザックDPで割り当てる」だけで達成されており、それでも青くらいのパフォーマンスが出たというあたりがalgo茶~緑くらいでAHC躊躇してる人にリーチすれば良いなとぼんやり思っています。

レーティングはこんな感じになりました。明らかに収束しています。黄色は遠い。

以上