[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
この記事が気に入ったらサポートをしてみませんか?