提出コード

https://github.com/Kyo-s-s/AHC014

やったこと

適当に貪欲したものを初期解とし、部分的に壊して再度貪欲し構築する焼きなましをしました。

盤面の持ち方

• 盤面の点の有無: boolを持つ64 * 64の配列を用意し、x, yを(x << 6) + y としてアクセスできるようにしました。

• 盤面の辺の有無: int を持つ64 * 64 * 8の配列を用意し、x, y, i(i:辺の向き)に対して(x « 9) + (y « 3) + iで辺がないなら-1, あるなら追加した四角形のidを格納するようにしました。

  これにより、ある四角形を消した時にそれに伴って消える四角形の特定が容易にでき、削除が比較的容易に書けるようになりました(実は必要なく、boolでよかった説があります)。

• 生成した四角形をすべて配列に入れていき、採用するもののインデックスを持つようにしました。使わなくなったら採用するインデックスのsetから消すことでよくなりました。

貪欲

• すべての点に対して「その点を使った四角形が作れるか？」を判定し、作れるなら作る…ということをしました。
  • 自分の対角線に新しく頂点を作る/自分の隣に新しく頂点を作る ことができるか？を判定することで、一度作れないと判定された点についてもう一度判定する必要がなくなってうれしかったです。
  • 最初はすべてのまた点が置かれていない箇所について四角形を作れるか？を判定していたのですが、重くて焼きなましの回数がカスだったので終了日前日に書き直しました。もっと早くに書き直すべきでした…

破壊

• 適当な点を選び、ランダムでその周囲のx個の点とそれを消したことによって消される点をすべて消しました。
• 中心を消してしまうとほとんどすべてが壊れてしまい、最初の貪欲と同じようになってしまいうまく焼けていなかった説があります(未検証)。

反省

• 盤面を一次元に直して持つようにしましたが、boolを持つのであれば64bit整数で持つほうが良かったかもしれません(コンテスト中に思い浮かんだのですが、縦横の移動が大変そう…となりやめてしまいました)。
• ビジュアライザが複数の出力に対応していなかったので焼きなましの過程を見るということができませんでした。頑張ってビジュアライザを改造し、焼きなましの過程を見てみるということをするべきでした。

感想

• 手元で複数ケースを回せるようにしたのですが、これはだいぶ良かったです。きちんと動いているかの確認がすぐ手元でできたため、実装をしよう！と決めた日はガンガン実装することができました。
• 前回に引き続きコードをGitで管理していたのですが、やっぱり戻したい！となったときや大規模な修正をしたくなったときに嬉しさを感じました。