AHC 014

AHC 014 でやったことのメモです。暫定 45.5M です。

忙しい人は最後の「まとめ」だけ読めばおけです。

9/17-19

親戚の結婚式を兼ねて家族旅行

9/18

移動中はできないと思っていたが、マニュアルモードでスマホでもできることに気付いたので遊んでみる

ぱっと思い付くのはこんな感じ。

中心付近にたくさんおいても大したことないので、なるべく「外側」に置きたい
中心付近に置くことで邪魔されないように、最も「外側」に行ける点を毎回選ぶのである程度点数が出そう？
これを数手先まで読んだりしてみる（例えば 2 手先で一番外側に行けるように、みたいに）のはアリ？
焼きなましみたいにする場合、「点の削除」が必要になるので、点と点の親子関係（ある点を消すには他のどの点を消さないといけないか）を保持しておくと良さそう？

9/19

実装の方針

なんか全く思いつかない。

9/20

とりあえずクラスを作ってみよう！

クラスの設計

使った格子点を記録（ $N^{2}$ 配列で愚直に持つ）
各格子点から出ている線の向きを記録（ $8$ 方向あるので $8$ bit で持てる → 必ず同じ方向だけ見ることにすると $4$ 方向で良いのでそちらを採用した。）
点の追加の判定・実行：追加する点とその対角にある点の座標および「軸に平行か、 $45$ 度傾いているか」を引数とすれば良い *1。 $(x0,y0)$ および $(x2,y2)$ を対角とする追加ができるかどうかを判定する関数と、実際に追加をする関数を定義した。
ランダムな点の追加： $N^{2}$ 点から $1$ 点、 $8$ 方向から $1$ 方向を選ぶことで点の追加ができれば行う

はじめての提出

何も思い付かないので「ランダムに点を追加する」のをたくさん行って、追加できなくなったら best_score と best_state を更新して終了する

のを時間いっぱい繰り返して一番良いものを選ぶだけのコードで出してみる。これで 32.9M 点。ループ回数は 50 回ぐらい。

正の得点を得ました #AHC014 pic.twitter.com/qVtCBVxz3Y
— きり (@kiri8128) September 20, 2022

Submission:

https://atcoder.jp/contests/ahc014/submissions/35013761

毎回貪欲に一番外側に置く貪欲方式も試してみたがあまりよくならないので断念。

9/21

今は 1 点を追加するときにランダムで追加する点を（ $N^{2}$ 点から）選んでいるが、最初に追加可能な点と方向のリストを持っておけばもう少し高速化できそう。

やってみたら 35.5M （切り捨て、以下同じ）で 111 位。ループ回数は 1000 回ぐらい。まずまず。

ちょい伸びでゾロ目 #AHC014 pic.twitter.com/LWKcNVSEDE
— きり (@kiri8128) September 21, 2022

Submission:

https://atcoder.jp/contests/ahc014/submissions/35024674

そう言えばいつも思うけど、 AHC だとコードテストで出力が全部出ないからデバッグしづらいんですよねー。結果をビジュアライザに貼りつけて動くことぐらいは確認したいけど、結果だけで出力制限に引っかかることが多い。「質問」で聞いてみたけどダメとの返答が *2 。。まあ手元でデバッグして、コードテストはループ回数とかどの処理に時間かかってるか調べるだけで良いか・・・。

9/22

いくつか高速化。

（毎ターンどこに追加できるか調べるのではなくて）追加可能点のリストを持って、この中からひとつをランダムに選ぶようにした
点を追加したときの追加可能点の更新を、追加した点から 8 方向で辿れるところだけ見るようにした

あと山登りじゃなくて焼きなましにした *3 。

これで 39.9M ぐらい。

計算量でどれぐらい違うのかを調べてみる。手元 Python とコードテスト PyPy で 4 倍ぐらい。得点にすると 1 割ぐらい違う。 PyPy と高速な言語だとだいたい 4 倍ぐらい違うと仮定して、手元時間をさらに 4 倍にするとまた 1 割ぐらい変わる。

期間長いし別言語への乗り換えも視野に入れるか・・・。

9/23

さすがに C++ とかを使うのはやだけど、 numpy ならワンチャンあるかと思って、 numpy に適したコードに書き換えつつ高速化をちょこちょこする。具体的にはこんな感じ。

選択可能な手の一覧を取得するのを $O(N^{3})$ から $O(N^{2})$ に落とした *4 。
クラスのテーブルを一次元化した。
その他、各クエリ処理で $x,y$ を明示的に計算せず、なるべく $xy\ (=x*width+y)$ のみを使うように変更した *5 。

9/24

上位層のビジュアライザ結果を見ると、密に詰め込まれていて無駄がない感じ。「詰まってる」感をうまく定量化できればプレイアウトする前の途中状態でも評価関数を作れるかも？

具体的には、各マスについて、埋まっているかどうかだけでなく、 8 方向のうち何方向の線が埋まっているか *6 によってペナルティを設定すれば良さそう。例えば最初の 2 方向を使うことはペナルティが大きいけど、 6 → 8 にするところはうまく使えている証拠なのでペナルティを小さくする。

→ やってみたけどいまいちなので戻した。。

9/25

やっぱり高速化ぐらいしかやることがない・・・。どうせアイデアないし numpy とか numba で高速化するのはあり？文法とかなんも知らないけど一週間あればなんとかなるのか？

numpy ちょっと試してみたけどよく分からん。。 numba はがんばればできる？もっと分からん・・・。 C++ は大変そうだし・・・

そういえば最近 Rust が流行ってるという噂があるな。・・・え？

9/26

なにもアイデアが

9/27

浮かびません。。

9/28

Rust 、なんか型がちゃんとしてるとかデバッグしやすいとか言ってたから初心者でも書きやすかったりしないかな。

とりあえず ABC の A ～ C 問題の Rust の提出を漁りまくって文法を勉強しよう。

環境ないのでテキストファイル（秀丸）で書いて AtCoder のコードテストに出してみる。型？なにそれ？ usize ってなんですか？ struct と impl なんですか？慣れない概念が多くてつらいけどこのへんはなんとかノリで A 問題ぐらいの計算ならできそう。

いろいろググってみたら「借用」とか「所有権」とか出てきてこれはさすがにいみふ。調べてもこういう場合には & を付けますみたいに書いてるのはあるけど、 & の意味がよく分からん。所有権というのは言いたいことはなんとなく分かった気がする。 *7

ただコンパイラさん、エラーが分かりやすいし候補とかも書いてくれてすごい（ここもしかして "&" 付けた方がいいんじゃね？とか "self" 忘れてない？とか教えてくれてイケメンか！ってなってた）。コンパイラのない世界で生きてきたんだけど、こういうもんなの？

Python コードは手元にあるので、それをちょっとずつ直訳してみる。むずそうなところは計算量とか多少サボって実装する *8 。

9/29

型変換 *9 に苦しめられたり、 "&" とか "*" とか "mut" をコンパイラさんに言われるまま付けたり消したりしながら、丸一日以上かけてなんとか計算量さぼりバージョンの移植がだいたいできた。ただ、なぜか結果を見るとまだ追加できる点が残っている。なんで？

9/30

RE もたまに出るな。なんでだ？

型変換と範囲チェックあたりがあやしい予感はしてたけどどうもよく分からん。手元実行していろいろ確認したいけど、コードテストの出力制限がしょぼすぎて、 ANS を出力すると盤面情報が出せないし、盤面を見ようとすると ANS が出力できないという状況でデバッグめちゃくちゃしづらい *10 。仕方ないので Random じゃない関数を作って Python で実行した結果と比較して少しずつデバッグ。

これも丸一日ぐらいかけて調べると主にふたつが悪さをしていることが分かった。どっちも unsigned の取り扱いが悪かったみたい *11 。ひとつは引き算したときにマイナスになってほしいから usize を i64 に変換してたつもりだけど、 usize 同士で引き算をしたあとに i64 変換してた。

もうひとつは $x$ 座標が $0$ 以上であることを確認するときに "if 0 <= x" みたいに書いてたんだけど、この x が usize だったのでそもそもマイナスにならなくて必ず true になってしまうみたいな話だったっぽい。。