estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014） 参加記・感想文

概要

estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）に参加して34位でした。

atcoder.jp

過去最高順位です。やったね！

上位50名に入って景品届くかと思ったのですが、住所書いてなかったので（登録時に住所書いてなくてもメールで確認来ると勘違いしていた？）景品は届きませんでした。残念・・・

本番コンテストで初めて効果的な焼きなましを使うことに成功しました。山登りから焼きなましに切り替えた時にスコアが上がると気持ちいいですね。

AHC016が始まるので、景気付けに今までサボっていたAHC014の参加記（のようなもの）を書くことにしました。

解法

焼きなましです。

  • 近傍は以下の2つ
    • ある点に依存する点を削除->ランダム再構築
    • ある点とそれ以降の点を削除->1*1の長方形を優先して作成
  • 焼きなまし前半に打つ点の数が多いと褒める感じのペナルティ入れるとスコア微増した
  • 焼きなましする際にターンの巻き戻しをする必要があるが、Stateのコピーではなく打った点（and 打とうとして打てなかった候補）の履歴を管理してrollback処理にした方が気持ち早かったのでやった

考えたこと

1日目

  • できるだけ点を打つ->できるだけ四角形を描くゲーム？
  • 中心から遠くに頂点を打つと高得点
  • 最初の点が少なく方眼紙が広いほど高い係数
    • N, Mの値で別ゲーになる？ビジュアライザ見ても縮尺のせいかよくわからない
  • 10分かけても問題文読みきれない・・・読めなくていいが
  • 初期点は真ん中に固まる
  • 条件が複雑（それは毎回そう）（語彙力）
  • 既存の四角形と辺を共有できない
    • 辺の上に3点以上あるとだめ
  • 四角形の辺は短くした方が良さそう？
  • どこに点を打てるのか、候補点を出したい
  • 1つ点を打つと、頂点に使った点から生やせる辺の方向が2つずつ減る
  • 外に点を打ちづらい！
  • やる気が終わった・・・何もせず2、3時間くらい経った。子育てなどをする
  • 貪欲をとりあえずかくか
    • 外側から打つ？
    • 小さい四角形から描くようにする？
  • State：配布されているツールのソースにあるStateを流用できそう？
    • ツールのStateは盤面で「既に打った点の集合」と、「描いた辺」を持っている
    • これに「打った点（順序あり）」をフィールドに加えないと出力できなさそう
    • 四角形を描けるかチェックするメソッドがあるが、これは使いづらそう。頂点を打つ候補を探すのには効率が悪そう
    • Web版のビジュアライザは格子にカーソルを合わせると描ける四角形の候補が出てくる。ここのソースは隠されている？
      • ということはこれをどう実装するかが問題のポイントになるっぽい、というメタ読み
    • 打つ点の「x座標」「y座標」「（四角形を反時計回りで描くとした時の）描き始めの方向」を指定すれば、描ける四角形は一意に定まる
      • 点を打ってない全格子点に対して8方向調べることでその時点で描ける四角形の候補を網羅できる
      • なので、「x座標」「y座標」「（四角形を反時計回りで描くとした時の）描き始めの方向」を引数にとって四角形が描けるか確認するメソッドを用意する
        • 方向決めて四角形の辺を描き始めて既に打っている点にぶつかったら90度回転させて始点に戻ったらOK
        • ツールのソースにあるDXY定数の添字を1ずらすと45度回転になるので、あまり複雑なことをしなくても実装できそう
        • 描いてる途中の（既にある四角形と被ったとか）うまく行く行かない判定は色々書く
    • 四角形を（描けるかチェックするだけでなく）描いてフィールドを更新するメソッドを用意する
    • Stateから出力するためのメソッドを用意する
    • Stateからスコア計算するメソッドを用意する
    • とりあえずこれくらいか・・・他にも色々必要になりそう。
    • スコア差分計算はまだまだ色々工夫できるのかなあ。
      • 辺に対しても「x座標」「y座標」「（四角形を反時計回りで描くとした時の）描き始めの方向」を持つ必要があったりするのかな・・・
  • とりあえず貪欲やってみる
    • 基準などはなく描ける四角形から適当に選んで描く
    • 29.7M
  • 見た感じ焼きなましとか結構やりやすそう？コンテストで焼きなましをかけたことがないので、書いてみたい。
  • 小さい四角形を書いていくのが良さそう？

  • これもし手書きだとしたら、以前wataさんが人手は大体DFSと言っていたような気がする（？）ので、DFSもうまくいきそう？
  • 順位表で30M行きたくなったので、選ぶ候補点の順番をシャッフルして解くのを制限時間いっぱい繰り返してベストを出力してみる
    • 2400回くらい繰り返せる
    • 36.0Mで提出時5位（！！）
      • 潜伏しすぎでは・・・怖すぎる
  • 焼きなましなど書いてみたい
  • 複数テストケースを回して統計情報を取れるようにしたい（今までサボっていた環境整備）
    • 参考にする:

  • ちなみにここまでのメモは元は手書きで、今（2日目の昼）PCで打ち直している。打ち直す段階で文章整理できるかな〜と思ったけどほとんどそのまま打ち直してる・・・

2日目

（1日目は頑張ってメモを書いてみたけど、2日目から壊れてしまう）（理由はチャレンジしてみたことの項で後述）

  • 無駄に候補を増やさない実装をした。（実装辛すぎる） 38.2M
  • 反復回数をログで吐くようにした。（コミットのたびに反復回数に気をつけるのは良い習慣だった）

3日目

  • 追加した点をランダムに選んで依存する点を全て削除する山登り 44.3M
    • DAGを導入し、依存しない点を追加し直す

4日目

  • 焼きなましにしたら52.5M
  • 気持ち良すぎる

5日目

  • optunaを導入して焼きなましパラメータ調整してみる（注：最後まで効果でず）
  • 強化学習とか考えてた気がする
    • ある点を打った時の平均スコアをヒートマップとして取っておく、みたいなノリで・・・全然上手くいかなかった
  • いい評価関数ないかとかも考えていた気がする
    • 構成要素：小さい四角の数、候補の数、現在の手数くらいしか思いつかなかった

6日目

  • リファくた

7日目

  • i番目を壊して小さな四角から作っていく近傍入れた57.5M

以降

  • プロファイラと睨めっこしながら反復回数増やす

解説との差分

  • なるべく点から全方向に線を生やす考えによる評価
    • 全然思いつかなかったけど、上位勢は結構思いついてるっぽい
    • 4方向フルで使えた方がいいよね、の気分になれなかった
  • ビットベクトルを用いて状態管理することによる高速化
    • これ全然知らんかった・・・次すぐ使えるのはこの辺か
  • □→◇を交互に作るとよさそうみたいな直感の精緻化
    • 1位解説の「固定パターン」やばすぎる

bowwowforeach.hatenablog.com

  • ある範囲のやつを全て削除・ある線で切って外側を削除する近傍
    • 変化大きそうという直感から全然思いつかなかった

penguin46.hatenablog.com

チャレンジしたこと・上手くいかなかったこと

今回新しくチャレンジしてみたことについて。

考察メモ

  • コンテスト前に「ゼロ秒思考」という本を読んで、影響されて、メモを積極的に取っていこうとした

ゼロ秒思考

ゼロ秒思考

Amazon

  • 横向きA4用紙1枚に1分で任意のテーマに対して4〜6行で思ったことをそのまま書く、というのが本で提示しているメソッド
  • 「1分で」書き出すのは考察メモ的に難しいが、「思ったことをそのまま書く」という部分は効果的な気がしたので取り入れた
  • A4用紙で考察メモして、後でPCで清書しようとした。1日目は頑張って転記した
  • 思ったことをそのまま書くと堂々巡りになる
    • 本曰く、書いたことが堂々巡りになるのはいいことで、そのうち思考整理されていい感じに収束するらしい（的なことが書いてあった気がする、うろ覚え）
    • 確かにいい感じに思考整理された気がするのだが、無限に堂々巡りさせていたらそのままでは考察記録として清書できない状態のメモが量産されてしまった。なので2日目から清書を諦めた。

実際に書いたメモ。読めない

optuna

  • 今まで面倒で入れてなかったけど重い腰を上げてついに導入した
  • ローカルで1並列でやってみたけどこれだと難しい。並列度上げたい、今度はクラウド環境用意しないといけない

デバッガ、プロファイラ

  • 今までIntelliJ IDEA Community版でRustコードを書いていたが、デバッガとプロファイラが使えない
  • 別にプリントデバッグでいいかと思ったけど、多分良くないので、お金を出してCLionを買った
  • デバッガとプロファイラがある環境最高という感情になった

感想

  • 開催期間2週間はだいぶ疲れた
    • しばらく体調が戻らなかった
  • 解説放送良かった
    • 見ただけで復習が終わった気分になってしまった（？）
  • 参加記を書く気が起きない
    • 書くと復習になるので、書きたいのだが
    • 「復習のための参加記の書き方」を模索しないといけない
      • 自分の解法を他人にわかるように解説する必要はあまりないはずなので、そこに時間をかけない
        • 上位勢と何が違ったかを自分がわかる形でかければOK、と割り切る
      • 他の人の解説を読むモチベーションでしかない
      • 文章として体裁がまともかどうか考えないことにする。長いツイッター。箇条書き。
      • 上位勢の解説を読んで得られた学びのメモに集中する。次からは。
      • 参加記という体で書く必要ないってコト・・・！？
  • どうやって復習しよう？
    • コンテストの開催だけでなく延長戦込みで予定表に予定入れるべきか
    • 写経がいいのか、解説読むだけで自分で再構成するのがいいのか
      • 再構成、モチベーション的にも難しいな・・・
      • 写経も大変だが・・・
  • 面倒臭いことをやればやるほどスコアが上がる

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の参戦記はこの記事よりいい文章になるといいなあと思っています。