[AHC014] estie プログラミングコンテスト2022

[Q] https://atcoder.jp/contests/ahc014/tasks/ahc014_a

47Mで暫定91位でした。
1. 小さい四角をたくさん作ったあと、
2. 頂点の削除＋設置を完全ランダムで焼きなましました。

焼きなましアルゴリズムの処女作になりました。
頂点の削除コマンドができると、無限に削除と設置を繰り返せる。
時間に比例してスコアが伸びる現象は、得も言われぬ快楽。
マラソンが高速化ゲームといわれる意味が、ちょっと分かりました。

反省は、特技が少ないので、大枠ができてからほとんど改善に至らなかったこと。

Q. 盤面管理どうしよう
次の2ルールを考慮。
1. どの辺も二度使用してはいけない
2. あらたに結ぶ線の途中に点があってはいけない

〆て、以下の管理をした。

 // 頂点の場所管理
 vector<vector<ll>> C;
 vector<vector<vector<ll>>> RC;

 // 使用している辺の管理
 vector<bitset<62>> var;
 vector<bitset<62>> hor;
 vector<vector<bitset<62>>> Rvar;
 vector<vector<bitset<62>>> Rhor;

 // 頂点から出ている辺の数
 vector<char> relations;

 // 上下左右、直近の頂点
 vector<vector<ll>> U;
 vector<vector<ll>> R;
 vector<vector<ll>> D;
 vector<vector<ll>> L;
 vector<vector<vector<ll>>> RU;
 vector<vector<vector<ll>>> RR;
 vector<vector<vector<ll>>> RD;
 vector<vector<vector<ll>>> RL;

ルール1. どの辺も二度使用してはいけない
どの長方形も、次の3種類の独立な長方形に分けられます。
a. x軸とy軸に平行な線を通るもの(水色)
b. 45度回転させて、x+yが偶数のもの(赤)
c. 45度回転させて、x+yが奇数のもの(緑)

b,cは座標を45度回転し1/2倍すれば、aの配列と同じ形になる。
アルゴリズムを分けずに処理できて楽でした。
この3種類は、互いに同じ辺を使用することはないので、分けて管理。

ルール2「あらたに結ぶ線の途中に点があってはいけない」
= 座標(x, y)から見て、上方向に一番近い点は何か、右方向に一番近い点は何か、を管理する。上下左右の4方向の配列を用意した。


・だいたいベスト盤面(1409805 Score)

直線からダイヤモンドを生成する動きを活かしたいと思う

しかし、活かせない。
何をしてもスコアが伸びず闇堕ちエンド。

・反省VTR
https://www.youtube.com/watch?v=eddDPITjzDc
・焼きなましの中身も評価値をもたせるべき
・random_playoutに重みをもたせる
・1点ごとに削除/追加ではなく、領域で考える
・新しい点を置くごとに、枠の数が維持されるか、減るかを見極める


https://atcoder.jp/contests/ahc014/submissions?f.User=merhorn