RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013） 参戦記・反省文

概要

RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）に参加して169位でした。

atcoder.jp

（景品対象者順位で140位だったため、飛び賞で景品をゲットしました！）

参戦記を書く予定はなかったのですが、思うところがあり、読んでもらうためというよりは自分の復習のために参加記的なメモを書くことにしました。解法より反省が主体となっております。

また復習として、上位解法記事を読んだ上で各記事に対して自分なりの気づきを書くことにしました。（読んだ記事にリンクを貼っていますが、ご都合悪い場合ご指摘いただけると幸いです:bow:）

最終解法

  • PCの移動パートと接続パートに完全に分離。移動パートを先に行う
  • PC種類の優先順はK!通り試す。各施行の持ち時間3/K!秒で以下の移動・接続操作を行う

移動

以下の1.~3.を順に行う。（1.をどれくらいやったら2.をやるかとかはお気持ちで判断している。つまりK*100-110手までは1.をやる・・・みたいな感じにしている、ここら辺の値の決め方は勘）

  1. PCをランダムで選んで1マス動かす遷移を試す
  2. 選んだPCを動かした結果、上下左右を見て接続できる同じ種類のPCが増えるなら遷移を採用
  3. 接続可能な同じ種類のPCどうしを辺で結んでUnion-Findして連結成分を大きくさせることを試みる
  4. 優先している種類で、連結成分の小さい順にソートして、順に以下操作
    • 移動方法をBFSで探索（他のPCをどかしたりしないのでうまく移動できないこともある）
  5. ランダムに7*7のグリッド及びその中に含まれる空白を選んで、接続できる同じ種類のPCの合計が増える移動をスライドパズルっぽいDFSで探索する
  6. （同じ種類のPCで固まりがち）

接続

  • 適当な順序でPCを選んで、接続できる同じ種類のPCがあれば接続する
    • 順序をランデムで決めてスコア評価、を時間いっぱいループ。スコアが一番良いものを採用

考えたこと

後から書いているので嘘が多い

1〜3日目

  • 文章が長いので頑張って読む
  • ビジュアライザのサンプル見たら読みやすくなるかも？->動くサンプルみたいなのはないっぽい
  • 読んだ
  • 入力はシンプルっぽい
  • Kが特殊。Kの値で別ゲーなのだろうか？
    • ビジュアライザのseedを変えて見ると、疎なケースと密なケースがある
  • 移動と接続パートがある
    • ケーブルは交差してはいけない。むず
  • 移動に使えるターン数は少ない。
  • 適当につなげてもあんまりいいスコア出ない
  • とりあえず1手動かす遷移を入れればよさそうだが接続の前に動かそうとしているのでスコア計算できない
  • とりあえず接続可能なPCの数が増えればよさそう？
  • 11.8k

4日目

  • 1手動かすだけだと途中で止まる。自分が見るだけでも2、3手動かしたり・ちょっとどかせばスコアアップするものが見つかる
  • とはいえどかし方がよくわからない・・・
  • とりあえず低確率で2、3手動かす
  • スコア上がらない。
    • 手数使いすぎ？
  • 残り移動15ターンになった時の遷移に入れておく
  • 12.8k

5日目

  • 接続するときに同じクラスタかどうか見るようにして13.9k
  • 最後繋げるPCの種類の順序を全パターン試す18.2k

6日目

  • 接続の順番をランダムでいろいろ試す
  • 最後に複雑な動きしないとくっつかないPCをどうしようとか考える
  • BFSして（UnionFind使って）くっつける20.1k

7〜8日目

  • グリッドを適当に切り取って適当に動かせば伸びる？
  • グチャッとした実装をする
  • DFS実装して20.3k

反省

自分がなぜこのような実装をしたのか覚えていないので反省点を出しにくい

  • 実装した時のコミットメッセージはなんとなく書いている。ので、何をしたかは覚えている
  • 何をしたかは覚えているが、なぜそんなことをしたのかは覚えていない
  • 考察が足りない実装、意味のない実装が多すぎる
    • 意味のない複雑さがある
    • 自分の解法を人に説明しにくいという弊害も生まれる（なんでそういう実装をしたんですか？という質問には答えられない）
    • 何がうまくいかなかったのかがよくわからない結果、上位者との差分が取りづらく、反省点を抽出しにくい

実装してうまくいった理由・うまくいかなかった理由についての考察が足りない

  • うまくいった時は「なんか上がった」だし、うまくいかなかった時は「なんかうまくいかなかった」で終わる
  • 統計情報（例えば、反復回数など）、ログをまともにとっていない。横着している
  • 何がどううまくいったか、うまくいかなかったかを文章にしたい
  • 今回の場合、接続してからのスコアと接続前の接続可能見込みで見た時のスコアの相関を全く見ていないのは明らかに良くなかった

コンテスト終わった後、上位陣の解説を読んでいない

  • 今まで解説を読んでも難しくてちゃんと読んでいなかったのだが、有識者に伺ったところ、ちゃんと読んだ方がいいらしい
  • 難解だが、専門書と思えば読めそう
  • 上位者と初手が絶対に違うはず。上位陣の最初の解答はちゃんと読んだ方がいいのではないか？

他の人の解説読んだ感想

解説ありがてえ〜。。以下気づきメモ

terry_u16 さん(18位)

www.terry-u16.net

焼くときの注意点として、ただ単にPCを移動させたり接続したり接続を切ったりするだけだとすぐに局所解にハマってしまい、より良い解を探すことができません。というのも、今回の問題では得点がクラスタのサイズの2乗和で決まるため、もしそのクラスタ内の接続を切ってしまうと得点が大きく下がってしまい、いくら焼きなましといえどそのような解を経由することは絶望的だからです。そのため、できるだけ接続を維持しつつ解空間が滑らかになるような近傍を作っていく必要があります。

  • 「問題の難しい部分が言語化された！」と思った。何が難しいのか整理しないままだったのがよくなかったなと。
  • 今後焼きなましができるできないはさておき、「焼きなましが難しいとしたら原因は何か？」「どういう近傍操作があると探索空間が滑らかになるか？」は最初のフックとして考えてみるとよさそう。

「各PCの移動操作列」と「PC同士の接続」を解として持ちました。両者の整合性が取れるよう十分注意しながら近傍を作成します。

  • 移動と接続を同時に焼きなまし。スコア計算がそのまま評価に使えるという点で移動と接続を分けるより同時に考える方が自然に見える（後から思えば・・・）
  • こういうの同時に考えようと思うと頭壊れそうな直感が働くから脳死で分けて考えがちだけど、ちゃんとメリデメ書いてどちらがシンプルにできるか比較した方がいいな・・・

あるPCが一度移動してきたマスはその後立入禁止という制約を付けました。これにより移動に関するPC間の依存関係がなくなり、独立に移動の追加・削除を行えるようになります。

  • 戻す近傍、全く発想になく！なんで思いつかなかったのだろう・・・直感的に履歴管理を嫌がったのだろうか。戻すに当たってどういう不整合が起こるかを整理する体力・余裕がなかった気がする
  • 一度通ったら立ち入り禁止はかなり大胆なように感じる。総移動が少ない、戻ったら立ち入り禁止も消える、直感よりうまくいくのか

bowwowforeach さん(1位)

bowwowforeach.hatenablog.com

移動と接続両方考えないといけない。

移動を確定させた時点で接続方法が定まるかどうか？簡単には定まらなそう。

  • 「簡単には定まらなさそう」が私には感覚で見抜けない・・・。しかし接続うまくいく率をとってみることは私にもできたはず。

  • 巻き戻し管理すごい・・・

  • 接続を持っているわけではなく「BFS起点PC」を持っている
    • 接続を持つことと比べてメリデメなんだろう？

wanui さん(4位)

zenn.dev

  • PCをどかす遷移を「多段退避」で行っている
    • すごい
    • どかす動かし方、どうやってやるのがいいかわからずスルーしていたけど、経路を先に決めてどかす候補決めて再帰か・・・
      • 完全に密じゃなければスライドパズルDFSじゃなくてこういうのもできるのか

manta1130 さん(34位)

RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）参加メモ.md · GitHub

  • 遷移したら差分計算ではなく最初からスコア計算している？
    • スコア計算重くても探索空間が山登りしやすければ焼きなますのよさそう
    • AHC009とか自分もこれをやって結構良かった気がする

次やること

AHC014ではいろいろやるぞ〜〜という意気込み集

今までサボってたけどこれからやる

  • 考えたことを書く。仮説と、検証したかどうかと、検証結果を書く
  • 状況整理を面倒くさがらない。焦らない。どれだけ整理して進められたかで自分を評価する
  • 自分ができる限り丁寧に、科学的にやる

詰まった時・実装前に問いを立てて問いに答える

良さそうな問いかけ一覧

初手

  • この問題は人間ならどう解くか？
  • 難しいポイントは何か？
    • 焼きなましが難しいとしたら原因は何か？
    • どういう近傍操作があると探索空間が滑らかになるか？

詰まった時

  • 今の解のよくない点は？
  • どうしたら良くない点が解消される？
  • 出せる統計情報は何か？
  • ビジュアライザでほしい機能は何か？

実装前

  • これを実装したときにどういう世界になっているか？

実装をしたらスコアが下がった時

  • 「こうした方が良さそうを超えるこうしちゃダメだった」は何か？

復習

  • 最終的な自分のやったこと・実装を、意図と共に説明できるようにする
  • コンテストが終わったら上位陣の解説を読む
  • やるべきだったこと・次やることを書く

まとめ

思うところあって参戦記（？）を書いてみたのですが、

  • 基本的な反省ポイントが多かった
  • 記録が雑でやったこと・考えたことを思い出せない
  • なんでこれやったの？みたいな実装が多く、何を反省すればいいかわからない
  • 文章が下手。長い文章をあまり書いたことがない

という事情から、ちゃんとした文章を書くことができなかった気がします。

AHC014の参戦記はこの記事よりいい文章になるといいなあと思っています。