第10回 Asprova プログラミングコンテスト参加記 (39.1M; 130位)

learningBOX株式会社開発部開発課 SREチームの松永です。

前回の記事ではバックエンドエンジニアなどと書いていた気がするのですが、人事異動にて最近新設されたSREチームに所属することになりました。

さて、アスプローバ株式会社 が主催する 第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023） に参加しましたので、今回はその参加記を会社の工数を使って書きます。

問題概要

詳細はコンテストの問題ページをご確認ください。以下概要です。

以下のように区画分けされた 20 * 20 の正方形で示される土地が与えられます
農機が左端のいずれかにある穴から出入りできます
農機は黒線で区切られていない箇所を東西南北に移動できます

あなたはいくつかの種を持っています
- それぞれの種 k は「S_k ヶ月目までに植える必要がある」「D_k ヶ月に収穫する必要がある」という情報をもっています
- 種 k を植えて収穫すると D_k - S_k + 1 のスコアが貰えます
100 ヶ月の間、以下の操作を繰り返します
- 月の開始時に農機で移動可能なエリアに種を蒔く
- 月の終了時に農機で移動可能なエリアから作物を収穫する
- ※未収穫の作物が存在する箇所は農機で移動できません。そのため、蒔いた当月にその奥にある作物を収穫するような動きはできません
収穫不可能な作物が存在するような矛盾を起こさず「何ヶ月目にどこにどの種を蒔くか」をいい感じに最適化して貰えるスコアをなるべく増やしてください

初日

参加登録はしていたのですが、 Asproba Contest ではなく Armored Core をやってました。

アクションゲーム苦手勢なのでダクソもSEKIROもエルデンリングも食わず嫌いしており、フロムソフトウェアのゲームはこれが初プレイでしたが試行錯誤を繰り返す感じが実質AHCみたいで面白いと思いました。(???)

二日目

重い腰を上げ、まともに問題文を読みました。

区間スケジューリングを最適化する定跡として、終了日が小さいものから処理するという考え方があります。

実質初日ということもあり、とりあえず様子見として

全マスに収穫日が近い順に蒔く ⇒ 全部刈り終えるまで蒔かない ⇒ 全マスに蒔く ⇒ 全部刈り終えるまで蒔かない ⇒ ...

というシンプルな方針で実装することにしました。

何を蒔くか(収穫日が近いもの)は決まりましたが、どこに蒔くかも決める必要があります。

これについては、入口に未収穫の作物が存在することで奥に行けなくなるのを避けるため、収穫日が近いものを入口に近い方に配置すればよいでしょう。
入口からの距離を求めるには幅優先探索などのアルゴリズムを用いればよいです。

def isValidMove(y, x, dy, dx):
    # 省略

moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
inf = 10**9
dist = [[inf] * W for _ in range(H)]

deq = deque()
deq.append((i0, 0))
dist[i0][0] = 0
while deq:
    y, x = deq.popleft()
    for dy, dx in moves:
        if not isValidMove(y, x, dy, dx):
            continue

        ny, nx = y + dy, x + dx
        if dist[y][x] + 1 < dist[ny][nx]:
            dist[ny][nx] = dist[y][x] + 1
            deq.append((ny, nx))

得られた距離の情報をもとに、距離が近い順に収穫日が近い種を蒔くことで、以下のような結果が得られました。緑部分は収穫日がD_kの作物が植えられていることを表します。波紋みたいで面白いですね。

この解法は暫定テストで 21,788,950 点を得ることができます。

システムテストとの相性によりますが、暫定テストでこれくらいのスコアの場合、最終順位で言えば 490 位ほど、パフォーマンスにして 1159 相当です。
これだけでもそれなりに高いパフォーマンスな気がしますが、入力がAtCoder参加者におなじみの移動可能マスを"."と"#"で示す形式ではないことや、矛盾なく配置するために最低限の探索アルゴリズムに関する知識が必要なため、ややとっつきにくい問題だったのかもしれません。

さて、上記のgifを眺めていると、

赤枠で囲んだような箇所について、「別に全部収穫し終えるまで待たなくても次を蒔いてしまっていいよね」という気持ちになります。

これは播種の条件を「あるマス以降に訪問するマスの全てに未収穫の作物が存在していないこと」とすればよさそうです。播種の開始地点は入口に限らず、その条件を満たしたマスということになります。

この手のチェックは深さ優先探索を再帰関数で実装するのが手っ取り早いですが、一旦最短経路をベースにして木構造を作った方が見通しが良さそうだと感じたことや、先に提出した解法との差分がわかりやすいということもあり、いったん探索部分は変更せず、隣接リストのようなもので訪問元(親)と次の訪問先(子)を管理することにしました。

具体的には、探索後の距離を用いる以下のようなコードを追加しました。
（が、冗長です。辺の重みが同じなので探索時に親子関係を更新すれば十分で、のちに修正しています）

parents = [[(-1, -1) for x in range(W)] for y in range(H)]
children = [[[] for x in range(W)] for y in range(H)]
for y in range(H):
    for x in range(W):
        mi = dist[y][x]
        for dy, dx in moves:
            if not isValidMove(y, x, dy, dx):
                continue
            ny, nx = y + dy, x + dx
            if dist[ny][nx] < mi:
                parents[y][x] = (ny, nx)
                mi = dist[ny][nx]
        ny, nx = parents[y][x]
        if (ny, nx) != (-1, -1):
            children[ny][nx].append((y, x))

なにはともあれマス同士の親子関係が整理できたので、後は子要素を端まで再帰的に見て、作物が無ければ再帰的に植えていけばよいです。毎回マスごとに再帰してると計算量がつらいので、入口から実行した結果をメモしておくとよいです。

この方法により、無駄なマスを相当減らすことができました！

この解法は暫定テスト時に 27,508,000 点でした。
こちらは最終順位で370 位前後、パフォーマンスにして 1350 程になります。

三日目

播種すべきマスやマスごとの親子関係に関してはある程度形になってきたので、この日は

「どの種を植えるべきか」

について向き合うことにしました。

二日目は区間スケジューリング問題のセオリーとして終了日が小さいものを優先して植えていましたが、これは本問題で言えば「マスが一次元に並んでいる」場合に「植える種の個数を最大化する」ようなアプローチです。

本問題は作物が栽培されている期間や数そのものを最大化する問題ではありません。(めちゃくちゃ重要)

実際にもらえるスコアはあくまでも D_k - S_k + 1 なので、「もっと後に植えてもいいものを今植える」行為は基本的に「S_k 日目まで土地を腐らせる」ことと同義です。

公式が提供するビジュアライザでは、マスごとのスコアへの寄与も表示することができます。二日目解法のgifではほとんど常に緑になっていたような場所でも、実際のスコアへの寄与は70前後のものが多いです。

栽培期間と実際にもらえるスコアとの差が小さく十分に蒔けていれば、この値は90以上にまで上昇するはずです。

そこで、三日目では各ターンごとの操作を以下のように修正しました。

種は S_k (作付の締切日)の降順に並べておく (seeds: list[Seed]) (期限切れのやつはリストから除く)
各ターンについて今まで通り「自身および子孫に未収穫の作物が無いか」を確認する
植えて良ければ、植える種の個数をカウントする (cnt)
seeds, targetSeeds = seeds[:-cnt], seeds[-cnt:] とし、必要個数分を締切の近い順に切り出す
targetSeedsを D_k (収穫日) の降順にソートする
targetSeeds.pop()しながら再帰的に入口側から播種先を決める

ざっくり

「蒔く対象は作付締切日を基準とし、どこに蒔くかは収穫日を基準とする」

という方針です。以下はマスごとのスコアの画像で、実際の播種日と作付締切日の時間差が小さくなったことにより無駄が減り、スコアへの寄与が 90 以上になるマスがたくさん出てきました。この辺の改善が一番楽しい。

gifは以下の通りです。

暫定テストのスコアは 34,064,525 点でした。最終順位は300位前後に相当します。

四日目

雷雨による気圧の影響かあるいはAHCに生活リズムを破壊されたのか、熱はないものの体調があんまり良くなかったのでこの日はリモートワークにしました。

AHCの方も、幅優先探索の順序変更を試したりして終わりです。

探索順によってグラフの形が変わります。グラフの形が変わるということは播種条件の満たしやすさが変わるということなので、これはスコアに寄与し得ます。

が、やはり27M -> 34Mのような劇的な変化というわけではなく、手元でいくつかの探索順を試して数十万点くらいは伸びそうだなと確認し、よさそうなものを提出して終了です。得点は 34,861,175 点でした。

五日目

体調が回復したので、この日は複数の改善案を試しました。

未収穫の作物があっても播種を試みる

今までの方法では、子孫に一つでも未収穫の作物がある場合、新たな収穫は行っていませんでした。

収穫日でソートして播種する種を決めていた序盤の方法では特に気にする必要がなかったのですが、
基準を作付締切日に切り替えたことで、奥の方に少し離れた未来の収穫日の作物が鎮座している場合が生じます。
また、まだ播種していない種の中に植えてもいい種が残っている可能性も生じてきました。

具体的には、奥に収穫日が D_i である未収穫の作物があったとしても、 D_j <= D_i を満たす種 j であれば播種してしまってもよいことになります。（そのような種 j は締切日に余裕がありまだ蒔かれていなかった種ということになります）
三日目の要領でそれらをtargetSeedsとして取り出し、ソートした上で再帰的に播種を試みました。

「実は赤の部分↓にも蒔ける(収穫日が小さい)種がまだ残ってるかもしれないから、蒔けるなら蒔こう」という感じです。

子孫が複数に枝分かれしている場合の考慮が面倒なので、この日は一旦末端の枝についてのみ対象として実装しました。

末端の枝の親子関係を最適化する

基本的に、同じ座標であれば長さ1の末端枝2つの方が長さ2の末端枝1つよりも扱いやすいはずです。
依存関係が1つ減るからです。

これは、最初の幅優先探索において距離の情報だけでなく末端の枝かどうかの情報も保持しておき、
末端でないマスを距離0とした多始点の幅優先探索を再度行うことによって「非末端枝からの距離」を求めることで改善できそうです。(探索順次第ではそんなことしなくてもいい感じにできるかもしれませんが)

複数の探索順を試し、その最大値を正式な解答とする

四日目の実験から探索順が寄与することはもうわかっているので、複数の探索順で解を求め、その結果のうち最も良いものを出力するアプローチを取り入れました。当然実行時間は伸びます。

これらの改善により、最終的に 36,066,100 点になりました。最終順位でおよそ260位台、パフォーマンスは1530台くらいのスコアになります。じわじわ伸びてますね。

三日目と五日目を比較すると以下のようになります。

三日目

五日目

植えてよければ再帰的に植えるようにしているので、枝が合流していくにつれて必然的に植えちゃいけない可能性が高くなります。それらの"通路"は画像中で薄い色として浮き出てくることになります。

五日目の解法では通路の形が三日目と比較して変化しており、最大スコアを取る探索順が三日目と異なっていることがみてとれます。

六日目

以下の順で改善を行いました。

五日目のアプローチを末端以外に拡張

五日目時点では末端の枝についてのみ未収穫の作物があっても播種を試みるようにしましたが、これを末端以外にも拡張しました。

具体的には、今までboolで保持していた「自身または子孫に種が植えられているかどうか」を表すフラグをinfで初期化された数字に置き換え、再帰の過程で自身や子孫の収穫日の最小値で更新するようにしました。

また、親側で今月何を植えるかを考慮しておかないと、より末端側の枝において改めて播種を試みた際に収穫日が逆転したりする懸念が出てきます。

これを回避するために、再帰的に最小値で更新された上限値だけでなく、下限値用の変数も用意しました。

探索順の取捨選択

先の改善により末端の枝に限らず播種をできるようになったのですが、各月ごとの計算時間が増えてしまったため、今度は「複数の探索順を試してスコアの最大値をとる」という五日目に行ったアプローチとの兼ね合いでTLE(実行時間制限超過)するようになってしまいました。

そこで、今までは雑にitertools.permutationで回していた探索順の列挙を事前に定義したリストを使用するように変更することとしました。

ローカルで自作のtester(Pythonのsubprocessを使用した単純なもの)を回してスコアへの寄与が低い探索順を洗い出してリストから削除することで、それなりに探索順を列挙しつつ時間内に間に合うように修正しました。

これらの改善により、スコアは 38,110,050 点まで伸びました。
最終順位は200位前後となり、パフォーマンスは 1670 程になります。

以下は五日目との比較となります。

五日目

六日目

左下のあたりがわかりやすいですが、(基本的には S_k を基準にしつつも)上限、下限を考慮しつつ「未収穫の作物があっても D_k の許す範囲内で播種を試みる」アプローチを適用したことで、通路上の色も濃くなっているのがわかります。

七日目

7日目で大きな改善につながったのは1つだけで、播種の優先順位の改善によるものです。

平均的には、作付の締め切り日が同じものが複数存在する場合、収穫日が後の作物を植えた方が良い結果につながると想像できます。より未来までスコアに寄与することを確約できるからです。（もちろん、個別にみると翌日にめっちゃ良い感じの種が残っている可能性はあるかもしれませんが）

未収穫の作物がある場合に蒔く際にはそのあたりの考慮が不十分だったので、D_kが大きいものを優先してとれるようにしました。

これにより、暫定テストのスコアは 39,084,750 点まで伸びました。

が、これ以上の改善案が全く浮かばず、小手先の探索順改善などで時間を溶かしていました。

八日目

最終日です。

が、小手先の探索順改善を続け、かけた時間の割に得られるものがほとんどないまま椅子を温めるお仕事をしていました。
（マスは十分に利用できていたので探索順の改善よりも播種部分を最適化するのが理想なのですが、39M前後に順位が詰まっていたため今から大きな変更をするより小手先の改善でも順位が変わりうるという判断でした。結果的には椅子を温めただけだったのですが...）

ほんの少しだけ暫定テストのスコアが上昇し(テストケースとの相性による誤差のレベル)、
39,105,850 点で最終提出を行ってフィニッシュです。