競プロ日記004: AHC014の反省
AHC014の復習（反省？）
AHC014では長期コンなのに頑張り切れなかったので，ちょっとだけ復習しておくことにしました．私の場合，MMとかAHCではとりあえずA*を実装することが多いです．よくあるパターンはpriority queueを使ってA*→良さげなら深さ毎にpriority queueを用意してビームサーチ的なものという感じなのですが，これだと結構な数の状態を保持することになるので，速度面でもメモリ面でも十分に最適化できていない状態でこの方針はマズい気がしました．そんなわけで最初にシンプルなDFSを書いてみたんですが，スコアがかなり低かったのでその理由だけ確認しておこうと思いました．
ランダムに負けてんじゃね？
最初の方の操作が後の方にどう影響してくるのかぜんぜんわからないので，DFSとか全く向いてないとは思いつつ，だからといって「ハイ焼きなまし！」みたいなこともできる気がしないので，それなりの評価関数なり枝刈りができればスコアはある程度上がるだろうと一旦書いてみました．案の定とてもスコアが低い．制限時間を延ばしたところで深いノードの周辺でもちゃもちゃやるだけなのであまり意味がないし，まあしかたないかなー．
でね，公式解説を観たんですよ，最初の30分くらい．そしたら負けてるんですよ，ランダム解に負けてる😭．さすがに情けないということで，何がダメなのかを確認しておきました．
小さい矩形を優先
これは最初から気付いていたので，「ですよねー」とか思いながら解説観てたら，小さいものを優先的にランダム配置したものに大きくスコアが負けていました．ここでビジュアライザ（アニメーション）を初めて使いました（遅い）．最初に小さな矩形を作ることができる場所は限られていて，以下の辺りだけです．
このとき，どちらからでも良いんですが，貪欲にみちみちっと点を打ち込んでいくと当然周辺が埋まります．埋まると別のところを埋めていって，全部埋まれば終わりという感じですね．
このようにした場合，上手くやれば埋められた部分がぽっかり空いてしまうことがあります．
ランダムに負けてるのはこれでした．試しに埋めきる前に他の部分に移動する方針にしてみました．
この方針で進めると，無事右下部分を埋めることができました．
まあとりあえず埋まったというだけで，上の方が全然ダメですが…．
反省
これはちゃんとビジュアライザを見て早期に気付くべきでした．あと手抜き実装として，DFSで解の更新がなくなった場合に適当に上の方のノードにジャンプするだとか，最初からやり直すとかしがちなんだけど，もうちょっと真っ当なやり方で改善していきたい😩
