カメヲラボ

主にプログラミングとお勉強全般について書いてます

競プロ日記003: AHC014とABC271

AHC014

AHCのレーティング2022年10月2日現在

AHC014終わりました! AHC(長期)の締め切りって日曜日の19時が多い気がするので,今回もそうだと思ってたら前日の土曜日だったんですね.締め切り20分前に気が付いて,とりあえずちゃんと動作しそうなものを提出しました.最終日に細々と実装しようと思ってたことができなかったのでちょっと心残りな部分はありますが,さっさとやらない自分が悪いのでまあ仕方ない.

感想

この問題は盤面の評価が難しくて,一通り点を置かないとスコアの良し悪しがわからないので,ものすごく難しいやつだと問題を読んですぐにわかりましたが,『じゃあどうする』が全然出てきません.こういう状況は最近多くて,ダメなことはすぐにわかるようになっても解決案がろくに出てこないという苦しい時期です.結局は自分にできそうなゆるふわビームサーチをやることになるんですが,MMと違って盤面がとても大きく,また制限時間も比較的少ないため強引な探索ではほとんどスコアがでません.この辺もよくわかっているハズなのに全く対処ができていない.少し時間をかけて戦術を考えておかないといけませんね.

基本方針

盤面が大きく探索が難しいのと,現状では高速化が不十分ということもあって,なかなか酷い方針だとは思うんですが貪欲ガチャしました.具体的にはZobristHashingで盤面を記録しつつ,(その点を置いたときのスコア) × 倍率 - (ペナルティ)を評価関数として貪欲に点を置きます.ペナルティは矩形のサイズの2乗と,縦横バランスとしました.つまり矩形が小さくて,正方形に近いものほど高評価になるようにしています.この評価関数で生成した盤面を記録し,同じ盤面はスキップするようにしつつ,スコアの倍率を変化させながら繰り返し実行する感じです.

とにかく初期の盤面の状態が悪ければどれだけ探索しても意味がないので,最初から何度もやり直して偶然良いスコアが出るまでやっただけですね.本当はそこそこ良いスコアが出た盤面に対して点の削除と追加を何度か行う処理を入れたかったのですが,間に合いませんでした.

データ構造

Nが最大61ということで,どう考えてもBitboard作れってことでしょ!と思って64bit整数の配列×4(縦横斜め)に辺の情報を持たせました.あと,矩形のデータは繰り返し生成しそうだったので一度作ったものはキャッシュするようにしました.これはそんなに悪くないはず.

ダメポイント

まあとにかく遅い.何が遅いかというと,毎回点を打つための候補を盤面全体に対してチェックしているので,これで探索しようとすると全然間に合わない.最初に候補の一覧を生成し,あとは点を打つたびに差分を取るようなことをしなければならないと思うのだけどこれができていない.あとは点を取り除く処理ができていないところで,依存関係を考慮しつつとなるとバグが出そうで作業を後回しにしてしまったところですかね.早い段階でこれが必要とわかっていたのに手をつけないのは反省しないといけません.

次回に向けて

ヒューリスティック問題のコンテストで実力を挙げるには,コンテストが終わった後どれだけ復習するかで決まるような気がしていますが最近はまったく時間が取れていないので,そこをなんとかせねばなりません.コンテスト終わる→溜まった仕事を片付ける→次のコンテストが始まってしまうの連続なので,おそらくどこかでお休みを入れないといけません.もちろん『お仕事』の😁

ABC参加4回目

AHC014の提出を終えてぐったりしている中,京セラプログラミングコンテスト2022(ABC271)に参加しました.今回も3問ですが,初めて解く順序を変えてABDの3問を解きました.朝から子どもの運動会を観に行って,帰って仕事して,仕事中にAHCの締め切りが土曜日ということに気付いて慌てて提出して…と,いろんなことがあって心身ともにかなり疲労していたんですが,まあ何とかなりました.D問題に関しては昔自分が書いた記事でDP解の復元について触れていたので,「これは間違いなくできる」と判断しました.しかし表(H)と裏(T)を逆にしてWA(´Д`;)あとはA問題をPythonで書いたので,B問題でC++に変えたときに言語選択ミスでRE.そうかそんなミスもあるね.やっぱり言語は常に統一した方が良さそう.

ABCのレーティング2022年10月2日現在

Cはちょっと考えてできそうな気もしたんですが,全く頭が働かない状態でやったら間違いなくバグを埋める自信があったのでやめときました.復習もたぶんしないかな.あと3~4回はレーティングが上がりそうだけど,そこから先は何らかの対策が必要になってきそう.何しよ.鉄則本?