education week MM ConstrainedPermutation
問題ページ
TopCoder
MMはじめたいなーと思ってchokudai contest 001をやったりしていたらeducation week MMというなんともピッタリなものが開催されるらしいのでもちろん参加することに。
初日
16:00
問題を読み始める。日本語訳のmarkdownをつくって問題の内容を整理する。
17:00
テスターのコードを読み始める。Javaの講義が役に立つ日が来るとは思わなかった… generationの部分を読むと生成方法がわかる。スコア計算は制約の数だけループ回していくだけなので簡単そう。
18:00
近傍状態の生成が簡単そう、スコア計算が簡単そうといったところから焼きなましっぽさを感じる。あとは制約を全部満たしたとするとトポソではい。
18:30
.jarの使い方をしらないので調べたりしつつpythonでまとめてテストケースを実行させるコードを書く
19:00
遷移確率の決定方法だったり実装がよくわからないなーと思ってググると診断人さんのブログ焼きなまし法のコツ Ver. 1.2 - じじいのプログラミングを発見したのでありがたく見ながら実装させてもらう。近傍状態の生成には交換を使った。
2日目
5:30
唯一よくわからなかった時間計測部分を調べる。とりあえずclock()関数でローカルで実行はできたのでexample testを出してみる。当然のように全てTLEした。
6:00
TopCoderのサーバー上だと時間計測用の関数がやたら遅いといった話は聞いたことがあったので色々調べる。rtdscは問題なく動くそうなのでそれを使うことにする。example testで秒数とサイクルをあらかじめ測っておいてsec_per_clocksを定数で埋め込んでおき、rtdscで測ったクロックを秒に直すようにした。#ifdefをつかってローカル実行と提出時の時間の測り方を切り替えるようにしたら便利だった。
7:30
example testで試したら時間計測は問題なさそうなのでfull submittionをする。676832.70点。上位陣を見て80万点代を目標にする。
8:00
javaのよくわからないところを調べる。ローカルでテストケースを複数生成してcsvで出力して各コードのスコアの状況を比較するところまでできるようにする。
9:00
ブログに書かれている改善を試してみることにする。rand()をxorshiftに書き換える。
12:30
近傍状態の生成を高速化する。時間を無視して実行して、高速化がどれくらい効果があるのかを見る。上がりはするが80万は見えない…
13:00
遷移確率をexpをつかって計算で求めるものに変える。温度の取り方とかよくわからないなあと思いつつ実装すると明らかにスコアがガタ落ちしている。自分の実装が間違っているだけかもしれないがよくわからないので一旦おいておくことにする。
13:30
SCCしてDAGにして初期状態をよくすることを考えてとりあえずSCCをする。
14:30
SCCをしてみた結果一つの巨大な強連結成分になっている場合が多すぎてあまり効果はなさそう。
15:00
高速化よりもスコア関数や近傍状態の取り方、そもそも焼きなましじゃないといった根本的な方を色々試したほうがいいかなあと思う。
15:30
山登りを試してみるとかなりスコアがよくなって、70万後半代が出る。解空間が焼きなましより山登りに向いているのかなあとか色々考えるが問題から解空間を理解するスキルがないのでよくわからない。
17:00
評価関数の高速化をやる。評価関数の部分にO(制約の数)をかけていたが交換する部分に関わっている制約以外は関係ないので高速化出来そうと思い実装する。…がバグっていて挙動がおかしい。一旦おいておくことにする。
17:30
近傍状態の生成で最初は大きく変化させ、後の方では小さく変化させるといったことを試してみる。一応スコアは上がる。
18:00
テスターをいじってNのサイズによってテストケースが並ぶようにして、Nが小さい方には強いといったことを確認できるようにする。
3日目
6:00
焼きなましと山登りを比較してみる。たまに焼きなましが勝っているが基本山登りが勝っている。
8:30
山登りが何回実行できているかを表示してみる。10^4～10^5回程度でもうちょっと高速化したいなあと思う。ボトルネックを測るためにプロファイラを使って見る。gprofを使うと関数ごとにどれだけ時間がかかっているか見れるらしいので使って見る。便利といえば便利だがもうちょっと細かい単位でみたいのでtimerクラスをつくることにする。
9:30
スコア関数が重いという当たり前の事実が発覚した。一回試したスコア関数の高速化を試してみることにする。バグを直すと10^6～10^7回程度実行できるようになり100倍高速化された。
10:30
提出するとrstdcに切り替えるのを忘れていて全ケースTLEをして0点になる(ア
13:00
近傍状態の生成で交換するパターンを複数試す。交換3回→1回、交換2回、交換3回を試すと交換3回→1回が一番高かったのでこれを提出すると811030.48点
14:00
調べてみると線形順序付け問題、(有向)フィードバック辺集合問題と呼ばれる種類の問題らしい。近傍に挿入を使う方法がでてきたのでこれを試してみることにする。
15:00
2数x,yをランダムに選びxの位置をyに挿入するという近傍状態の生成を試す。スコアが明らかに下がる。交換近傍と合わせたりしたが全体的に下がっているため挿入近傍は捨てる。
16:00
トポソしたような一列のグラフとして考えるとある要素を指定したとき移動した際に最も点数が高くなる位置は貪欲に求められそうなので近傍の生成にこれを使おうとしてみる。…が明日からJAG合宿で時間がないのでここで終了。
最終的な方針
山登りをする。近傍状態の生成には交換近傍を使い、最初は3ペアを交換、最後の方は1ペアを交換とした。
最終提出のときのコード
#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; // ------------------提出前に確認！！！！！！---------------- #define MAIN #ifdef MAIN double cycle_per_sec; unsigned long long int begin_cycle; unsigned long long int getCycle() { unsigned int low, high; __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high)); return ((unsigned long long int)low) | ((unsigned long long int)high << 32); } double getTime() { return (double)(getCycle() - begin_cycle) * cycle_per_sec; } #else double begin_time_clock; double getTime() { return (double)(clock() - begin_time_clock) / CLOCKS_PER_SEC; } #endif unsigned int randxor() { static unsigned int x=123456789,y=362436069,z=521288629,w=88675123; unsigned int t=(x^(x<<11)); x=y; y=z; z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } class ConstrainedPermutation { public: // 制約の数、制約 int K, constraints[250250][2]; // 制約を隣接リストでもつ vector<int> cnt[1010][2]; vector<int> permute(int N, vector<string> con) { // 現在の状態 vector<int> currentSeq(N); // 初期化 for(int i=0; i<N; ++i) currentSeq[i] = i; // 制約を扱いやすい形に変換 K = con.size(); for(int i=0; i<K; ++i) { string tmp = ""; for(char c: con[i]) { if(c == ' ') { // I constraints[i][0] = stoi(tmp); tmp = ""; } else { tmp += c; } } // J constraints[i][1] = stoi(tmp); // IはJ未満 I<J cnt[constraints[i][0]][1].push_back(constraints[i][1]); cnt[constraints[i][1]][0].push_back(constraints[i][0]); } // 時間計測の測定 #ifdef MAIN cycle_per_sec = 0.00000000035631341763; #else begin_time_clock = clock(); #endif // ベストの状態、ベストスコア、現在のスコア vector<int> bestSeq = currentSeq; int bestScore = getScore(currentSeq); int currentScore = bestScore; // このスコープ内を時間いっぱい繰り返す { #ifdef MAIN begin_cycle = getCycle(); #endif const double duration = 9; const double starttime = getTime(); const double endtime = starttime + duration; double currenttime = starttime; while((currenttime = getTime()) < endtime) { int len = 50; if(endtime - currenttime < 4) len = 20; else if(endtime - currenttime < 2) len = 10; for(int i=0; i<len; ++i) { // ランダムに入れ替える int swapnum = 6; // swapnum個の被らない数をランダムに取る int x[6]; for(int i=0; i<swapnum; ++i) x[i] = randxor()%N; for(int i=1; i<swapnum; ++i) { while(1) { bool flag = true; for(int j=0; j<i; ++j) if(x[i] == x[j]) flag = false; if(flag) break; x[i] = randxor()%N; } } int nextdiff = 0; for(int i=0; i<swapnum/2; ++i) { nextdiff += getScore(currentSeq, currentScore, x[2*i], x[2*i+1]) - currentScore; } int nextScore = currentScore + nextdiff; // 状態遷移 if(nextScore > currentScore) { currentScore = nextScore; for(int i=0; i<swapnum/2; ++i) { swap(currentSeq[x[i*2]], currentSeq[x[i*2+1]]); } } } } } return bestSeq; } #define MAX_N 200000 // okな制約の数を返す // 数列seq、交換する前のスコアはprevScore、x番目とy番目を交換 int getScore(vector<int> seq, int prevScore, int x, int y) { int ok = prevScore; // xより小さいはずのindexがi for(int i: cnt[x][0]) { if(i == y) { if(seq[x] > seq[y]) ok--; else ok++; } else { if(seq[i] < seq[x] && seq[i] >= seq[y]) ok--; if(seq[i] >= seq[x] && seq[i] < seq[y]) ok++; } } // x以上のはずのindexがi for(int i: cnt[x][1]) { if(i == y) { if(seq[x] <= seq[i]) ok--; else ok++; } else { if(seq[i] >= seq[x] && seq[i] < seq[y]) ok--; if(seq[i] < seq[x] && seq[i] >= seq[y]) ok++; } } // yより小さいはずのindexがi for(int i: cnt[y][0]) if(i != x) { if(seq[i] < seq[y] && seq[i] >= seq[x]) ok--; if(seq[i] >= seq[y] && seq[i] < seq[x]) ok++; } // y以上のはずのindexがi for(int i: cnt[y][1]) if(i != x) { if(seq[i] >= seq[y] && seq[i] < seq[x]) ok--; if(seq[i] < seq[y] && seq[i] >= seq[x]) ok++; } return ok; } int getScore(vector<int> seq) { int ok = 0; for(int i=0; i<K; ++i) { int x = constraints[i][0], y = constraints[i][1]; if(seq[x] < seq[y]) ++ok; } return ok; } }; // -------8<------- end of solution submitted to the website -------8<------- int main() { ConstrainedPermutation cp; int N, K; cin >> N >> K; vector<string> constraints(K); for (int k = 0; k < K; ++k) { int i, j; cin >> i >> j; constraints[k] = to_string(i) + " " + to_string(j); } vector<int> ret = cp.permute(N, constraints); cout << ret.size() << endl; for (int i = 0; i < (int)ret.size(); ++i) cout << ret[i] << endl; cout.flush(); return 0; }
まだよくわかっていない点
* 焼きなましの温度と遷移確率の決定方法について
* 解空間を想像する能力
* ローカルテストのときにJavaのマルチスレッドをつかって高速化する
* 点数アップ
コンテストに参加して得た知見
* 大筋の方針を色々試して点数が高いものを決定できてからパラメーター詰めとかを始める(それはそう)
* 時間計測はrtdscをつかう
* 焼きなましの実装（近傍状態の高速な生成、評価関数の高速化）
* ローカルテストの方法
他の方が使っていたが自分が考えなかった方針
* 入次数、出次数をもとにソートして初期状態の決定
* 最後に考えていた貪欲で候補が複数あればもっとも遠い位置に移動
感想
unratedですがリアルタイムでMMに参加できていろいろ知見が得られた。最後の方針を実装したかったなあといった気持ち。焼きなましっぽいといったところまではたどり着いている人が多そうなのでそこからの近傍状態の生成や高速化、温度の取り方といったところをちゃんと詰められるようにしないと良い順位は取れなさそう。初心者なりにがんばっていきたい。
gitのローカルリポジトリをつくってコードを管理するようにしたら結構便利だった。あと1人slackをつかって思いついたことを書くようにしていったら便利だった。タイムスタンプがあるのでブログを書く時に楽。
