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、と割り切る
      • 他の人の解説を読むモチベーションでしかない
      • 文章として体裁がまともかどうか考えないことにする。長いツイッター。箇条書き。
      • 上位勢の解説を読んで得られた学びのメモに集中する。次からは。
      • 参加記という体で書く必要ないってコト・・・！？
  • どうやって復習しよう？
    • コンテストの開催だけでなく延長戦込みで予定表に予定入れるべきか
    • 写経がいいのか、解説読むだけで自分で再構成するのがいいのか
      • 再構成、モチベーション的にも難しいな・・・
      • 写経も大変だが・・・
  • 面倒臭いことをやればやるほどスコアが上がる