はじめに.現在9月23日です.せっかく順位が悪くないので参加記を書こうと思います.べ,別に,スコアが伸びなくなって飽きたとか,早期撤退しようとか,そういうわけじゃないんだからね!?勘違いしないでよね?
先に言っておくと,私は,山登り法とか焼きなまし法とか名前は知ってるけど理解はしてないし,今回行なったのがそのうちのどれかなのか,それとも違うのかも分かってないです.むしろ本物の焼きなましのほうが詳しいまである.なんなら焼き入れ,焼き戻しまで(ry).
なので,どちらかというと,「ヒューリスティックの知識や経験があまりないけど,ひとまずそこそこの点数を取りたい!まず何から考えていけばいいの?」って人向けの参加記かもしれません
※10月1日追記. 最終的に暫定テストで55Mまでいきました.
一言でいうと,辺が重ならないような長方形を作ることができる点を選んでいく問題.
選択可能な点のうち,どの点(長方形)を選ぶか,その最適化問題.
問題ページより→
20Mまではシンプル.全部0で提出するだけで14Mになるみたい.初期配置のM個の格子点から繋ぐことのできる格子点を全部つなげば,新たな候補を探索しなくてもひとまず20M超えると思う.例えばseed0の初期配置では,右の水色の格子点を用いて長方形が作れる.条件を満たしつつ重複しないように選んで出力するだけ.方針とかは特になく,点の探索,スコア計算,辺が他の長方形と重複していないか,などの基本的な機能の実装がメイン.(ただし,探索部分は結構実装が面倒.あと,普段のAtCoderの書き捨てのコードではなく,長期コンテストなので後々困らないように関数やクラスはどう設計すればいいか悩んだ).
「候補の格子点から一つ選ぶ->その格子点から各方向に新たな候補となる格子点を探す」を繰り返す.新たな格子点を探すのは,20Mまでに実装したコードが使えるので,問題は「どの候補(格子点,長方形)をどの順番に選ぶか?」だと思う.ランダムに選んで時間いっぱい回す,というのも一つの方法だが,あまり効率は良くなさそう.「点数が高いものから選んではどうか?」とも考えたが,ビジュアライザをマニュアルモードで少し遊んだ感覚では,あまりよさげには感じない.結果的に,「長方形の辺の長さが小さいものから選ぶ」という方法を選んだ.例えば次のような場面を考える.
左下の図の水色の格子点を選ぶとする.このとき,赤の長方形と緑の長方形の2つを選ぶことができる.当然どちらを選んでも,この1回の操作で増える点数は同じだが,問題の条件より,長方形の辺上に格子点は存在できない.もしかしたら,後々,紫のような長方形を追加したい!なんてことが起きるかもしれない(というか起きる).「長方形の辺が長い」=「その後配置可能な格子点や長方形を減らす」ことになるので,なるべく選びたくない.したがって,priority_queueを使って,辺が短い順に長方形の候補を取り出していくということをした.時々ランダムで使わない操作もいれた.ちなみに,この時の長方形は後述のRectという名のクラス(構造体)を作って管理.この結果,32Mまで到達.
さて,ここからいよいよヒューリスティックみが出る.30Mまでの解法は乱数を入れているので,繰り返した分だけ違った解が得られる.中には,ビジュアライザを見ながら,ちょっといじったら点数伸びるのになーって解もある.そこで,「点数が上位だったものは残しておいて,それらの後半を再構築する」という操作を行なった.俗にいうビームサーチ(のはず).以上.
ここでは方針よりも,プログラムの書き方のほうが重要かも.解の数だけデータサイズも増えるので,どのように管理するかで実行速度やメモリ使用量に大きな差が出た.c++の話だが,いくつもある解を,直接,値で管理するのは好ましくないので,私の場合は,shared_ptrを用いた.解を探索してくれるSolverというクラスを作っておき,Solverが出した解が高得点だった場合,vector<shared_ptr<Solver>>で管理.使わない,点数の低いものは時々捨てる.これでMLEも防ぐことができる
40M~50Mはかなり色々試したので,主なものを挙げる.
・priority_queueのCompare変更
30M解法のところで紹介した,辺の長さが短いものから順に取り出す方法.ただ,より高得点を出すには,これだけでは足りなかった.具体的には,点数の高い点や辺の座標,長方形の細長さなどを優先したpriority_queue使った.長方形の細長さ!?と思うかもだが,これは以前のショートケーキAHCの時に,誰かがケーキが細長くなるように分割するって話をしてたので,半分ネタでやってみたらそこまで悪くなかったので採用した.実際,有効なのかは微妙なところだけど,多様性にはつながると思う.
・上位以外の解も後半再構築
初期解の時点で,解後半を再構築するというもの.これは微妙.スコアが安定はするけど,当然時間を要するので,高得点も出にくくなる.ケースバイケース.
・シンプルに高速化
乱数を使う以上,試行回数は何より大事だと思う.例えば格子点や辺を管理している配列は毎回作らず,可能な限り使いまわす.40M解法の「後半を再構築」する際も,候補の格子点を再度全部探索せず,変更する部分のみうまく探索するなど.他にも,例えばグリッドの管理,最初vector<vector<bool>>(N*N)にしてたけど,array<array<bool,MAXN>,MAXN>>にしたら2割くらい早くなった.あと,一応試してみたのは,pair<int,int>を一つのintで表現すると早くなると聞いたが,ほとんど速度変わらず,可読性が著しく落ちたので元のpairに戻した.
・パラメータ調整
これは50M目指すとき以外も常にやってはいる.ただ,この段階で,N,Mの値次第でスコアや選べる長方形の差がかなりあることに気付き(遅い),N,Mごとにビーム幅や各パラメータを変更した.
そのほか思いついたものを片っ端から試しはして,特定のケースには極端に強いものなんかはあったけど,万能なものは少なかった.
本日AHC最終日.50Mまでしかいかないと思ってたけど,55Mまできたので追記.
40M解法のところで,「点数が上位だったものは残しておいて,それらの後半を再構築する」のうち,再構築部分を改善した.後半部分はその都度再構築されるが,前半部分は使いまわしになる.最初はいいが,試行回数を重ねるごとにマンネリ化され,多様性が生まれなくなってしまう.そこで,「点数が上位だったものは残しておいて,各解について,選ぶ長方形は変えずに選択順のみを入れ替えた解を作り,それらの後半を再構築する」に変更する.たとえば,長方形A,長方形B,長方形Cの順で選択した解を,長方形A,長方形C,長方形Bの順に並べ替える.ただ,もちろん任意の長方形同士を入れ替えられるわけではない.長方形Cは長方形Aのあとにしか選べない,といった条件も多々ある.これはいわゆるトポロジカルソートを行い,入れ替え可能な長方形同士を適当な優先度で選んでいく.ここが,今AHCで一番アルゴみを感じた.優先度については,中心が優先,x座標が小さいものが優先など,10通りからランダムに選択した.
最終的にまとめると,
①辺の長さや座標をもとに,適当な初期解を作る
②初期解のうち,高得点のものは残してビームサーチ
③高得点解の前半をトポロジカルソートで入れ替え,後半は再構築.ビーム幅狭めながら時間いっぱい回す.
って感じ.どうにかして多様性を増やすことができれば,60Mにも行くんだろうなと思ってる.
右図がseed0で一番良かった解で,975856点です.(クリックで解法展開できます)
176
11 13 12 13 12 12 11 12
13 13 12 12 11 13 12 14
13 14 12 14 12 13 13 13
11 14 12 15 13 14 12 13
10 14 11 14 11 13 10 13
11 15 12 15 12 14 11 14
10 15 9 14 10 13 11 14
13 15 12 14 11 15 12 16
9 15 10 15 10 14 9 14
13 16 12 16 12 15 13 15
10 16 9 15 10 14 11 15
9 16 8 16 8 15 9 15
11 16 10 16 10 15 11 15
17 12 18 13 19 12 18 11
10 17 9 16 10 15 11 16
11 17 12 17 12 16 11 16
17 13 18 13 18 12 17 12
9 17 10 17 10 16 9 16
13 17 12 16 11 17 12 18
9 18 8 18 8 17 9 17
10 18 9 17 10 16 11 17
19 11 18 11 18 12 19 12
13 18 12 18 12 17 13 17
11 18 10 18 10 17 11 17
19 13 18 12 17 13 18 14
14 17 13 16 12 17 13 18
10 19 9 18 10 17 11 18
14 16 13 16 13 17 14 17
7 17 8 18 9 17 8 16
13 19 15 19 15 18 13 18
9 19 10 19 10 18 9 18
14 15 15 15 15 16 14 16
16 17 15 16 14 17 15 18
14 18 13 17 14 16 15 17
8 20 9 20 9 19 8 19
14 14 13 14 13 15 14 15
16 16 15 16 15 17 16 17
14 20 13 19 14 18 15 19
7 19 8 20 9 19 8 18
7 18 8 18 8 19 7 19
14 13 15 14 14 15 13 14
14 12 15 13 14 14 13 13
7 16 8 16 8 17 7 17
13 12 14 12 14 13 13 13
6 17 7 18 8 17 7 16
20 12 19 12 19 13 20 13
13 11 12 11 12 12 13 12
14 11 15 12 14 13 13 12
6 18 7 18 7 17 6 17
14 10 15 11 14 12 13 11
13 10 14 10 14 11 13 11
23 14 22 13 21 14 22 15
19 14 18 14 18 13 19 13
20 15 19 14 20 13 21 14
17 14 18 15 19 14 18 13
17 15 18 15 18 14 17 14
19 15 18 14 17 15 18 16
20 14 19 14 19 15 20 15
21 13 20 13 20 14 21 14
16 14 17 15 16 16 15 15
16 15 15 15 15 14 16 14
16 13 17 13 17 14 16 14
16 12 15 12 15 13 16 13
16 11 17 12 16 13 15 12
17 11 16 11 16 12 17 12
18 10 19 11 18 12 17 11
17 10 18 10 18 11 17 11
16 10 17 11 16 12 15 11
15 10 16 10 16 11 15 11
16 9 17 10 16 11 15 10
17 9 16 9 16 10 17 10
14 9 15 10 14 11 13 10
15 9 14 9 14 10 15 10
16 8 17 9 16 10 15 9
15 8 16 8 16 9 15 9
17 16 16 16 16 15 17 15
17 17 18 17 18 16 17 16
17 18 16 17 17 16 18 17
16 18 17 18 17 17 16 17
19 16 18 16 18 15 19 15
17 19 18 19 18 18 17 18
19 17 18 16 17 17 18 18
16 20 15 19 16 18 17 19
19 18 18 18 18 17 19 17
20 17 19 16 18 17 19 18
20 16 19 16 19 17 20 17
21 15 20 14 19 15 20 16
22 14 21 14 21 15 22 15
23 15 22 14 21 15 22 16
23 16 22 16 22 15 23 15
23 13 22 13 22 14 23 14
22 12 23 13 22 14 21 13
21 12 22 12 22 13 21 13
22 11 23 12 22 13 21 12
23 11 22 11 22 12 23 12
20 11 21 12 20 13 19 12
21 11 20 11 20 12 21 12
22 10 23 11 22 12 21 11
21 10 22 10 22 11 21 11
20 10 21 11 20 12 19 11
19 10 20 10 20 11 19 11
20 9 21 10 20 11 19 10
21 9 20 9 20 10 21 10
18 9 19 10 18 11 17 10
19 9 18 9 18 10 19 10
20 8 21 9 20 10 19 9
19 8 20 8 20 9 19 9
18 8 19 9 18 10 17 9
17 8 18 8 18 9 17 9
18 7 19 8 18 9 17 8
19 7 18 7 18 8 19 8
16 7 17 8 16 9 15 8
17 7 16 7 16 8 17 8
18 6 19 7 18 8 17 7
17 6 18 6 18 7 17 7
21 16 20 16 20 15 21 15
21 18 20 17 21 16 22 17
21 19 22 19 22 18 21 18
20 19 21 20 22 19 21 18
19 20 18 19 19 18 20 19
21 17 22 17 22 16 21 16
23 17 22 16 21 17 22 18
23 18 22 18 22 17 23 17
24 17 23 16 22 17 23 18
24 16 23 16 23 17 24 17
18 21 19 22 20 21 19 20
20 18 21 18 21 17 20 17
19 19 20 19 20 18 19 18
20 23 18 23 18 21 20 21
18 20 19 20 19 19 18 19
20 20 19 19 20 18 21 19
19 24 18 23 19 22 20 23
16 21 18 21 18 20 16 20
15 20 16 21 18 19 17 18
16 19 15 19 15 20 16 20
15 22 17 24 18 23 16 21
21 21 20 21 20 20 21 20
14 21 15 22 13 24 12 23
14 22 15 22 15 24 14 24
12 19 14 21 15 20 13 18
17 25 16 24 20 20 21 21
15 21 14 21 14 20 15 20
11 19 12 19 12 18 11 18
13 21 14 22 15 21 14 20
16 22 15 22 15 21 16 21
12 20 11 19 12 18 13 19
13 22 14 22 14 21 13 21
17 22 16 22 16 24 17 24
13 20 12 20 12 19 13 19
17 21 16 20 15 21 16 22
19 25 17 25 17 24 19 24
10 20 9 19 10 18 11 19
17 27 14 24 16 22 19 25
9 21 10 21 10 20 9 20
11 20 10 20 10 19 11 19
12 21 11 20 10 21 11 22
11 21 12 21 12 20 11 20
10 22 11 22 11 21 10 21
12 22 11 21 12 20 13 21
11 23 12 23 12 22 11 22
13 25 11 23 12 22 14 24
13 27 17 27 17 25 13 25
11 25 13 27 16 24 14 22
11 24 13 24 13 25 11 25
10 23 11 24 12 23 11 22
10 24 11 24 11 23 10 23
9 23 10 24 11 23 10 22
9 22 10 22 10 23 9 23
8 21 9 22 10 21 9 20
8 22 9 22 9 21 8 21
7 21 8 22 9 21 8 20
7 20 8 20 8 21 7 21
6 19 7 20 8 19 7 18
6 20 7 20 7 19 6 19
5 19 6 20 7 19 6 18
5 18 6 18 6 19 5 19
まず,最初に考えるのは格子点や辺をどう管理するかかと思う.格子点は(N*N)のbool型,辺は(N*N*4)のbool型で管理.上述の通り,最初はvectorだったが途中でarrayに変えた.4というのは,x,y方向+斜め2方向(z,wと名付けた)の4方向.
そのほか,探索用にvector<set<pair<int,int>> 型で既に使った格子点を入れた.探索の際には,xyzw各方向に隣り合った格子点を探すことが多いので,setを用いた.
次に,2つのクラス(構造体)Rect, Solverを作った.以下に主要なメンバを大雑把な紹介.Rectは長方形に関するデータと関連する関数を持つ.
struct Rect{
pair<int,int> p;//新たに追加する格子点
int v[2];//長方形の対角格子点へのベクトル
int type;//平行か傾いているか
bool is_available(格子点,辺){}//この長方形は条件を満たしているか?
void useThisRect(格子点,辺){}//格子点,辺の配列を更新する
};
struct Solver{
vector<Rect> ans;//解に使うRect保持
void search(p)//格子点p周辺の新たな候補探索
void solve(que){}//候補の格子点,長方形を採用するか否か,採用したらその格子点からsearchする
void derive(ans, que){}//上位の解法を受け取って,後半を再び選びなおす
void restruct(que){}//既存の解について,トポロジカルソートで長方形の選ぶ順番のみ変える
ll calcScore(){};
};
使う際は,
shared_ptr<Solver> solver(new Solver());
solver->solve(que);
って感じ.priority_queueのCompareを複数使いたい,けどその都度作るのは時間ロスするなー.ってことで,priority_queueを予め作っておいて,solveの参照型引数にするって結果に落ち着いた.
あとは,priority_queueに使った比較関数たちを以下に.多いので,展開式にしておく.説明難しいので,なんとなく察してください.
bool cmp0(Rect& a, Rect& b){//外周短くて,スコアが高いものを優先
if(a.length!=b.length) return a.length>b.length;
if(getScore(a.p)!=getScore(b.p)) return getScore(a.p)<getScore(b.p);
return a.dist>b.dist;
};
bool cmp1(Rect& a, Rect& b){//細長いもの優先
if(a.length<=1||b.length<=1) return a.length>b.length;
if(getAsp(a.v)!=getAsp(b.v)) return getAsp(a.v)<getAsp(b.v);
if(getScore(a.p)!=getScore(b.p)) return getScore(a.p)<getScore(b.p);
return a.dist>b.dist;
};
// type0 even方向
bool cmp2(Rect& a, Rect& b){
if(a.type==0&&a.left==0) return false;
if(b.type==0&&b.left==0) return true;
if(a.type!=b.type) return a.type>b.type;
if(a.length!=b.length) return a.length>b.length;
if(getScore(a.p)!=getScore(b.p)) return getScore(a.p)<getScore(b.p);
return a.dist>b.dist;
};
// type0 odd方向
bool cmp3(Rect& a, Rect& b){
if(a.length!=b.length) return a.length>b.length;
if(a.type==0&&a.left==1) return false;
if(b.type==0&&b.left==1) return true;
if(a.type!=b.type) return a.type<b.type;
if(getScore(a.p)!=getScore(b.p)) return getScore(a.p)<getScore(b.p);
return a.dist>b.dist;
};
// - 方向
bool cmp4(Rect& a, Rect& b){//
if(a.length!=b.length) return a.length>b.length;
if(a.type!=b.type) return getScore(a.p)<getScore(b.p);
if(a.type==0&&b.type==0) return abs(a.p.se-C)>abs(b.p.se-C);
if(a.type==1&&b.type==1) return abs(a.p.fi-C)<abs(b.p.fi-C);
//if(getAsp(a.v)!=getAsp(b.v)) return getAsp(a.v)<getAsp(b.v);
if(getScore(a.p)!=getScore(b.p)) return getScore(a.p)<getScore(b.p);
return a.dist>b.dist;
return a.type>b.type;
};
// | 方向
bool cmp5(Rect& a, Rect& b){//
if(a.length!=b.length) return a.length>b.length;
if(a.type!=b.type) return getScore(a.p)<getScore(b.p);
if(a.type==0&&b.type==0) return abs(a.p.se-C)<abs(b.p.se-C);
if(a.type==1&&b.type==1) return abs(a.p.fi-C)>abs(b.p.fi-C);
//if(getAsp(a.v)!=getAsp(b.v)) return getAsp(a.v)<getAsp(b.v);
if(getScore(a.p)!=getScore(b.p)) return getScore(a.p)<getScore(b.p);
return a.dist>b.dist;
return a.type>b.type;
};
//中心から
bool cmpP0(const Pii& a, const Pii& b){return abs(a.fi+a.se-2*C)>abs(b.fi+b.se-2*C);}
//左から
bool cmpP1(const Pii& a, const Pii& b){return a.fi>b.se;}
//右から
bool cmpP2(const Pii& a, const Pii& b){return a.fi<b.se;}
//下から
bool cmpP3(const Pii& a, const Pii& b){return a.se>b.se;}
//上から
bool cmpP4(const Pii& a, const Pii& b){return a.se<b.se;}
//外から
bool cmpP5(const Pii& a, const Pii& b){return abs(a.fi+a.se-2*C)<abs(b.fi+b.se-2*C);}
//左下から
bool cmpP6(const Pii& a, const Pii& b){return getZ(a,C)<getZ(b,C);}
//右上から
bool cmpP7(const Pii& a, const Pii& b){return getZ(a,C)>getZ(b,C);}
//右下から
bool cmpP8(const Pii& a, const Pii& b){return getW(a,C)<getW(b,C);}
//左上から
bool cmpP9(const Pii& a, const Pii& b){return getW(a,C)>getW(b,C);}
この欄を作っておいてなんだが,ローカルにAHC実行環境なんてない.順位表などを見ると,私の提出回数が突出して多いと思います.理由は簡単で,ローカルに自動テスト実行環境を作ってないからです.そのため,デバッグ作業を除き,基本seed0のみ,たまにseed1を試して,良さそうだったら提出してスコアを確認していました.これまでこの方法で困ったことはなかったので,よかったのですが,今回初めて問題が起きました.点数伸びそうな方法実装して,ローカルでseed0,1試すとかなり良い結果なのに,提出するとスコアが下がってるということが多々ありました.おそらく,Nの大きさやM個の初期格子点の分布による影響だと思います.自動テストの必要性を感じたので,次回の長期コンテストでは導入しようと思います.
※10月1日追記.簡易的な自動テストはできるようにした.といっても,ノートPCの性能の関係もあり,50ケース程度しか結局回してない.
上位解法の予想であり,実装力と気力があれば試してみたかったなーって妄想解法です.しばしお付き合いください.
①前提として,四隅に近づくほど高得点になる
②初期配置の座標は,N/4<=x,y<=3N/4の範囲内
--->いかに四隅の格子点を取れるかが重要なのでは?まるでオセロだな(?)
seed0がどれだけあてになるか分からないが,共有されたビジュアライザを見てると,高得点(90万点以上)のものは斜め方向に伸びてる気がする.
じゃーどうすれば四隅がとれるか?
平行,斜め,平行...を交互に組み合わせれば,四隅方向に拡張できそう.ただし,同時に複数方向に拡張するのは難しそうなので,一方向のみ拡張してはどうか
何てことをもとに,解法を考えてみた.
ある四隅,例えば右上の,座標(N,N)方向に拡張するとして,まず(N,N)付近の点を一つ決める.この格子点が右上になるような長方形を適当に作る.その長方形のほか3点に対しても,また長方形を作って..とすると,再起関数で表せそう.一見O(N**N)になりそうだけど,メモ化再起でN*N程度まで計算量落とせる?再起関数を辿っていって,すでにほか3点が使われている長方形を見つけたら,再起関数を戻りながら辿ってきた長方形を答えに入れる.そして,ほか3点が使われているというのは,言い換えれば初期配置格子点まで帰着したということ.
ここまで書いて,あれ?先に四隅の格子点を決め打ちすれば再起関数で出来そうだし,中心付近や初期配置格子点からたどればdp[i][j][k]:=座標i,jの格子点で~って条件を満たす長方形は作れるか?という重実装アルゴ問題に落とし込めるのでは?という結論に至った.長方形の条件の確認がめちゃくちゃ大変そうだけど.
より具体的な内容は,この余白には書ききれないので読者への宿題とする.
2週間というかなり長いコンテストだった.正直,ちょっと長すぎやしないか?個人的には,AHCは3日間くらいのコンテストが月2くらいだと嬉しいな(無理をいうな).writerさんいつもありがとうございます.
今回の問題は,個人的には簡単だったのかな?と思ってる.例えば,前回のAHCなんかは,サーバーを動かして,つないで,手数制限もあってと,行動の幅も制限も複雑に感じた.無限通りありそうだと思った.一方,今回のは,どの長方形を選ぶかという行動しかなく,作れる長方形の上限なども設定されていない.とにかく作るだけなので,やろうと思えば全通り試すこともできそう.もちろん実行時間は到底間に合わないけど.
terryさんのseed0,100万点ビジュアライザなんかを見る限り,どうやら上(9月23日)の解法予想は外れらしい.グリッドの四隅ではなくて,むしろひし形?◇?みたいな形になるみたい?実行時間が長ければ,私の解法でもseed0で95万くらいまではいく.ただ,5sという限られた時間では85~90万が多い.55M解法で多様性について軽く触れたが,スコアが上がれば上がるほど,多様性の大事さを実感した.やみくもに高得点ばかり残したビームサーチだとすぐに多様性がなくなり,ほとんど同じ買いが量産され,すぐにスコアが伸びなくなる.これがいわゆる局所解か~と,身に染みて実感した.
コンテスト当初,順位表の1ページ目にいて,どーせすぐ落ちるだろうと思ってたのに,ふたを開ければ最終日まで2枚目と3枚目の間を行ったり来たりしてた.正直予想外.ヒューリスティック緑,まだAHCも3回?くらいしか参加していない自分にしてはかなりの大健闘.おかげで研究もせずAHCにのめりこみ,110submitを超えた.
AHCはイチゴケーキを除き,毎回ビームサーチしてる.けど,ビームサーチを向上させるには多様性が必要で,そのためにはアルゴが結局重要なんだなーと感じた.ローカルテストも大事だなと.入力次第でかなりスコアや解が変わるので,暫定テスト連投評価だけではどうしても特定のケースにのみ強い解しかできないなと.今回せっかくローカルテスト作ったので,次回以降も再利用していきたい.
昨夜,コンビニに行った.空がきれい.無数の星が見える.あ,オリオン座だ.真ん中に並んでる3点,RectJoinしやすそうだなー.なんて思ってみたり.AHCを2週間やり続けると,星をRectJoinしてしまう不治な病にかかります.時間をかけて,ゆっくりリハビリしていきます.
だらだらと長い記事をここまで読んでくださり,ありがとうございました.