SRM 712 div2 med RememberWordsEasy
考えたこと
O(max(d_1,d_2)max(w_1,w_2))で愚直にDPするのは無理。考察の方針が思い浮かばなかったのでとりあえず手で試してみる。区間の端を0単語とすると1～d1までの和の単語数までは全て実現することが可能そう。区間の端を決め打ってその区間で実現できる最小と最大の単語数を考えた時、その間の単語数は全て実現することが可能そう。したがって、d1日目に覚える単語数を決め打てば、そのときに実現することが可能かどうか判定できそう。
O(w_1)で探索していくコードを書いて提出するとシステスで落ちた…実装がバグっている部分を直して提出を繰り返したら5WAくらいで何とか通せた。
学び
無駄に場合分けを増やして混乱してバグらせるをしない。
こういう問題はちゃんと数式をまとめてから書き始めないと自分はバグらせるのでちゃんと紙にまとめる。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a <= x && x < b) #define MP make_pair #define PB push_back const int INF = (1LL << 30); const ll LLINF = (1LL << 60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; class RememberWordsEasy { public: string isPossible(int d1, int d2, int w1, int w2) { REP(i, w1 + 1) { // d1日目をi単語 // semester1で[low, high]単語覚えられる ll low, high = (ll)d1*(d1-1)/2 + i*d1; if (i <= d1) low = i*(i+1)/2; else low = i*(i+1)/2 - (i-d1)*(i-d1+1)/2; if (low <= w1 && w1 <= high) { // semester2で[low, high]単語覚えられる ll low, high = (i+d2)*(i+d2+1)/2 - i*(i+1)/2; if(i == 0) low = 0; else if(i <= d2+1) low = (i-1)*i/2; else low = (i-1)*i/2 - (i-d2-1)*(i-d2)/2; if(low <= w2 && w2 <= high) { return "Possible"; } } } return "Impossible"; } };
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をつかって思いついたことを書くようにしていったら便利だった。タイムスタンプがあるのでブログを書く時に楽。
JAG夏合宿2017参加記
初日
歩いていたらICPCの話をしている人がいておーとか思いながらオリセンに向かう。早く着いてしまって暇だったたのでtwitterリストを作りながらチームメンバーを待つ。周りの人々がみんなレッドコーダーに見えてこわい。
チームメンバーと合流した。2人しか来ていなかったので一人の人とmergeしてもらいYang33さんと出ることに。
手分けしてABCを読むとどれもそこまで自明な問題ではない。Bが二部グラフでは？（嘘）とかAでうまく文字を使っていけば算数すれば解けそうといった話をしていると後ろの問題が解かれている。Aでうまく文字を使っていく方法について相談していると気づいたらdivさんがJを通していた。Dが解かれていたので読んでいると気づいたらdivさんがKを通していた。Dは算数をすればいいので実装すると通る。Aの実装に交代してEを読む。BNFがあるのでそのまま構文解析かと思ったがvectorとexprをうまくまとめて扱わないとだめでどうしようとか考えているとAとHが通っている。チームメンバーにEを相談するとまとめて扱える構造体か何かがあればよさそうと言われ実装してくれた。その間にsolvedが多かったFの"極小"文字列を読む。sum(T_i)が105なのを使うんだろうなあとか検索っていうとtrieとかSAとかかなあとか思っているとEが通っている。この時点で残り1時間くらい。文字種jがi番目の次に出てくる位置を覚えておけばO(T_iの長さ)でできるじゃん！とか話しているがよくよく考えると開始位置の候補が多すぎる…尺取りみたいに開始位置、終了位置をずらすとか3分探索とかSAとか色々考えるが不可能でコンテスト終了。
チームでは6完だか個人では1完（ア
このコンテスト中にfor文すら書いていない…コンテスト終了後に問題文を読み直しているととんでもない事実が発覚する。最小の部分文字列を探す問題を解こうしていたが"極小"の文字列を探す問題だった…誤読に気づくと前後から貪欲すればいいのではい。3人で誤読していて悲しいね。
TLの人々がボドゲをしているのを観測したので遊びに行く。TLでよく見るプロ各位が大集合していてボドゲ会が開かれようとしていた。競プロerは地頭力が強いのでみんな強くてすごかった。Coupとコードネームをやった。Coupは最初に動きたくないから早く10枚にはしたくないけどコインを集めないとコインレースに負けるジレンマのバランスのとり方とかブラフとか難しいなーといった感じだった。
2日目
翌日、無事起床AC
ボドゲをした人々と朝ご飯に行く。ご飯とパンが別の場所にあるため貪欲に取ると大量に炭水化物を食べることになる罠を無事切り抜け朝飯を食べる。貪欲に取っていったらナップザック問題の最適化に失敗してお腹がMLEしている人々がいた。
コンテスト前にチームメンバーを募集しているとゆらふなさんに組んでもらえることに。マクロや開発環境とかの確認をしつつコンテストの開始を待つ。
記憶が曖昧なのでちょっと違うかも。
前の方は難しいらしいので後ろから手分けして読む。Jがぱっと見自明だが制約を見ると何もわからない。Lが読解が少し不安だけどそこまで難しい問題ではなさそうといった感じ。順位表を見るとBとGが解かれていてチームメンバーが読んでいたので残りの問題を読んでみることにした。Iを読んでみるとコンビネーションの和で整数を表せればいいらしい。上の桁(?)のから取れるぎりぎりの大きい数を貪欲に取っていくみたいな気分になったが証明ができない。Bの実装に入っていたがWAが出ていてつらそうなのでいっしょにデバッグをしているとゆらふなさんがGをAC。Lの読解がおそらく最初のであっていて解ける問題ということを確認する。順位表を見るとBH,次いでIJが解かれているといった感じなのでHを読む。borderingって何？隣の方がenergy低いの違和感がすごいし端に移動するのか？といったことを考えたりしているととゆらふなさんがLをAC。borderingについて相談するとやっぱり隣では？と言われる。問題として隣と一個飛ばしは確かに自然ではあるのでその方向で考察することに。この時点でBがかなりハマっていてつらい感じ。Bのデバッグをチームメンバーがしてくれている間にHの考察を進めることに。SとFが端にあるかどうかで場合分けしていく。両方とも端にない場合まずFがない方に移動をはじめないとだめで～といったことを考えていると、num/3+num%3+(端にない数), num = f-s-(端にない数)といった式が出て来る。これを一回実装して出すとWAになる。Bの実装に一旦交代し考え直す。制約をよく読むとs<fとは限らない。BがACされたのでこれを直して提出するとAC。この時点で4完で残り1時間半くらい。Dが似たような問題を見たことがあったのでクエリを逆読みすると各頂点一回しか見ないのでみたいな話をするが距離d以下の点を列挙するパートが難しい。Fも少し考えるが順位表通りやはりI,Jをやろうという話に。蟻本の数論のあたりを読むとそれっぽいことが書かれているがやはりmodが素数でないのでだめそう。残り30分くらいで最初に考えていたIの貪欲を実装してみることにするが、二分探索をバグらせたりオーバーフローの扱いを間違えたりいろいろ実装を手間取ってるうちにコンテスト終了。
大体ゆらふなさんに助けてもらっていて申し訳なさがある。ICPCの弊チームは個人が勝手に練習が基本でチーム練習をあまりしていないのでもうちょっとチーム戦に慣れたい。
divさんとチームaotenjouの皆さんと夕飯を食べる。初心者の育成は大変とかするめが少なさ過ぎてレートが上げられないといった話をする。1年生に競プロを布教するのはやっぱりどこも大変なんだなあといった気持ちになる。
この日はこどふぇすの予選があったので色々準備しつつゆっくりする。ネットを求めて談話スペースに行くとプロ各位がすでにいらっしゃったのでお話したりしていた。コンテストではAで用意したcodefestival2017を使わなくて残念とかBで2倍を忘れて10分掛けたりDは全く違う方針で1時間半突っ走っていたりした。thanksボーダーには遠かったが3完それなりの速さでレートがもらえたのでよかった。コンテスト終了後はいつものtwitterのみたいなやりとりがリアルで展開されていておもしろかった。
3日目
日本時間を理解しているので起床AC。朝ご飯を食べてシーツと鍵を提出する。チームメンバーを1人募集しているとravenさんに組んでもらえることになる。今日は難易度順に並んでるのでは？ということで前から読んでいこうといったことを確認しつつ準備する。
ABCを分担して読む。ぼくはBを読むことになった。やること自体は簡単そうだけどバグらせそうなやつだなあと思い気をつけながら考察しているとdivさんがAをAC。Bを実装しはじめるが途中で考察漏れに気づく。Cが考察が終わっているみたいなので実装を交代して考察をし直すことにする。冷静に考え直すと別に難しいことはない。Cの実装を待ちつつDの考察に加わることにする。Nの制約からまず明らかにbitDP。残っている人が与えられたときに最適な行動はレートが1位か否かで場合分けすればできそうといった話をする。しかし遷移が2^nかかりそうなので合計O(4^n)に思えて計算量がオーバーする。Cが詰まっていたので交代してBを提出して通してCに交代する。Dの計算量が落とせる気がしないのでEの考察をしてみる。+だけなら自明。*をうまくつぶして+に置き換えるみたいなことを考えるがどうやればいいんだろうなーといった感じになる。順位表を見るとDEFが解かれているのでFも読むことにする。手元で色々実験しているとある頂点がcurrentに含まれると次のステップで隣接した点がcurrentに含まれてさらに次のステップでまたcurrentに含まれることに気づく。一回currentに含まれると偶奇が一致するステップでは必ず含まれることが分かる。なので最初に偶数ステップ目と奇数ステップ目でcurrentに含まれるタイミングを求めれば答えがわかりそう。ただ頂点を2倍取ってBFSすればいいだけだが謎の勘違いをしていて実装で詰まっていたら教えてもらって通せた。Fの実装をしている間にEの考察を進めてもらっていて先に×を前計算してから+を計算すればよさそうといった感じになっていた。ただ実装がめちゃくちゃ重そう。Eを詰めつつDの計算量の落とし方について色々考えたりする。Eが実装は重いが一応計算量的には問題なさそうといった感じになりdivさんに実装してもらう。Dの計算量が一向に落とせないのでGを読む。N,M,Kの制約が非常に小さいので色々できそう。ravenさんの考察に口をはさみ色々考察をすすめる。普段なかなか見ないような計算量が出てくるが確かにできないことはなさそう。が、実装が重すぎてできる気がしない。divさんのEがサンプル全て通ったらしいのでそっちを考えるのに集中する。提出するとWA。long long intを一箇所直して提出するとWAが減る。バグを消せれば通せそうということで3人でバグを探すことに。色々試してみるが通らなさそうなケースがない…そうこうしているうちにコンテスト時間が終了。
終了後にEのハックケースが見つかって直したらACに。Gの想定解法を読むと方針は合っていたらしい。DはO(4^n)ではなくO(3^n)のbitDPができるので計算量が問題ない。個人的にはFを思いつけたのはよかった。BもFも実装をつまらせたのは反省。
プロ各位とちょっとお話をして帰路につく。
コミュ障でもTLでよく見かける方とは話せたのでやはりtwitterは大事。コンテスト+ボードゲームで楽しい3日間だった。 参加記を書くまでがJAG合宿らしいのでJAG合宿を終えました。お疲れ様です。
chokudai contest 001
問題ページ
Tasks - Chokudai Contest 001 | AtCoder
唐突にマラソンがやりたくなったのでジャッジが公開されているマラソンのchokudai contest 001を試しにやってみることにした。
6:46 問題を読む グリッドゲーで操作にかかる手数をできるだけ小さくしたいらしい。
8:40 プロ各位のマラソン入門ブログを読み漁る。時間で殴る、問題の性質をちゃんと理解する、探索空間をうまくとるあたりが大事らしいことを学ぶ。とりあえず正の点数を取れるプログラムを出すことにする。1以上のマスがあったらそのマスから右下左上の順でいけるところまで行くコードを出す。0indexで出力して1回WAをもらうがとりあえずAC。541378点で202位/224相当。80万点で本番の上位50%みたいなのでとりあえずそこを目標にいろいろ試すことにする。
9:20 手元で試せるようにテストケースをつくる。本番10個らしいしそこまで偏らなさそうと思ったのでとりあえず15個用意した。いちいち実行するのはアホらしいのでpythonでまとめて実行したりそれぞれのテストケースで実行時間を測れるようにしたのをつくる。
盤面と開始するマスを決めればそのマスから一手番で取れる最長の取り方は決まる。右下左上の順で適当に探索するのからその最長の取り方に変える。サンプルを実行してみると長さ1の取り方ばかりしている。よくよく考えると1から100の均等配置で偶然並ぶ確率はだいぶ低そう。とりあえず出すだけ出す。544856点で予想通り低い。
10:30 何をしていいかよくわからなかったので有名アルゴリズムのビームサーチをとりあえず実装することにする。ビームサーチの1世代を1手番にしたりすればいいのかなあとか考える。queにvector<pair<int, int>>をつっこめばできないことはなさそう。計算量について考える。世代数×ビーム幅×遷移数とかになりそう。遷移数はO(HW)、世代数はこれまでの結果を見るに50000くらいになりそうで、1手番を選ぶのにO(HW)掛けているので大体k510^8くらいになりそう。ビーム幅kかなり小さい気がするけど大丈夫なのか…？
13:30 大きい値のマスから開始するものを先に選ぶようにすれば連続で並ぶ列ができやすいのでは?!と考えてとりあえず出す。510000点で最低記録を更新した。あとから考えると連続で並んだ列の数のどこかと同じ数があれば連続で消せるのに別の方に飛ぶのでこれが論外なのはそれはそう。
14:20 ビームサーチをしても幅が小さいと1手番で1マスしか操作できず、評価が難しい最初のほうでいいのが消えて結局いいのが残らないのではと思ったりする。焼きなましの方が向いているのか？と思ったりしたが焼きなましとビームサーチの違いもよくわからないのでうーん。
とりあえず1手番で何マスも操作できるようなのをどうやってつくるかが鍵っぽい？一回連続で並んだマスをつくればそこを何回も取れそうで連続列をつくっていくのが大事そう。(20 19 18 17 16と並んだマスをつくれば16回1手番で5マス操作ができる) 適当にやってたところで連続列はあんまりできなさそうだし連続列をうまく作ってやるのが大切そうに思える。
15:00 LISみたいなものを求めてその列に対して手番を行うを繰り返すとかを思いつく。
2日後の5:00 LISのを実装することにする。バグらせまくる。途中経過を見ると1手番で多くても6,7マスしか取っておらずそんないい影響はなさそう。
7:00 ようやく実装ができたのでとりあえず出すが572649点とそこまで上がらない。連続列をつくる方針は良いと思うのでもっと長い連続列をつくれるような貪欲を書いてみることにする。途中で小さい数が来ると短い列になってしまいそうなのでできるだけ大きい数の方向に進んでいくような列をつくってその列に対して操作を行うとした。
8:35 バグらせつつようやく実装を終える。737247点で161位/224相当でようやくマシな点数を出せた。
9:00 全てのマスを始点として試して、最も長い列であったものに対して手番を行うと変えてみる。むしろスコアが下がった。
10:40 大きい数を入れると連続にするために使う手数が増え、小さい数を入れると列の長さが減る。長さNの連続列があったとき、もっとも悪い取り方をするとN*(N+1)/2手番なところをN手番で取れるのでO(N2)からO(N)への改善となることを考えると列が長い方が大事そう。
10:55 考えてても何もわからなかったので途中でつくっている列の長さだったりを表示してみる。大きい数の方に進んでいく貪欲のコードを2番、長い列を貪欲に選ぶコードを3番と呼ぶことにする。列の長さの平均は6から7くらいで予想より短かった。(10くらいはあると思っていた。)想定どおり3番が2番よりも長い列を選ぶことはできていたが全体のスコアは低い。
11:30 最初の連続列30個で手数を見てみると、3番の方が7000手近く多い。そこからの手数消費は2番よりも小さいくらいなので最初が問題そう。連続列の長さに対する手数の比率を表示してみると2番は30から40くらいなのに3番は50近くいっているものもある。つまり連続列の中に大きく外れた数が存在する…？
12:00 連続列の決定方法として差が小さい方に貪欲に進んでいくとする。（これを4番と呼ぶ） 提出すると742553点で156位/224相当。一応上がった。あとは時間を全然使ってないのでこの時間をつかって探索して連続列をもっとうまく選べないか考える。連続列の選び方でビームサーチすることにする。
12:30 ビームサーチの実装を何となく考える。BFSからちょっと変えればいいだけに思えるので実装する。
queue<state> que
while(que.size()) {
priority_queue<state> pq
// このループでビームサーチ1段分の探索をする
while(que.size()) {
top = que.top
// top の状態から遷移したのを pqに突っ込む
}
// pqの上位k個をqueに突っ込む
}
13:00 評価関数の部分をどうするか悩む。とりあえず連続列から手番の操作を生成するコードをコピーしてきて 手数/連続列の長さ を評価関数の値として返すことにする。
15:00 バグらせ続ける。pop忘れて無限ループとか評価関数で例外処理が抜けてる部分があったり色々とひどかった。
翌日の4:00 手数の操作を順番に求める必要はないので評価関数をちょっと軽くしたりして改善する。とりあえず動くようになった。スコアがむしろ落ちている。TLを無視してビーム幅を長くしてみると大してスコアが上昇しない。評価関数をただの手数に変えてみる。大してスコアは上がらない。atcoderとローカルの実行時間の比較のためにとりあえず出してみる。ローカルで7秒くらいのを出したら4.3秒しかかかっていない、atcoder優秀。ローカルの2/3くらいになるかなーといった感じ。
4:30 評価関数を手数/連続列の値の和としてみる。連続列の長さの比よりもこっちのほうがよさそう。提出すると787405点で136位/224相当でいい感じ。
6:00 評価関数をいじったり、貪欲と合わせたりいろいろしたがスコアはむしろ下がる。
7:00 ビーム幅調整とか色々するがスコアが上げられる方針が一向にみつからない。
8:00 連続列を選ぶところをビームサーチの遷移にするようなのを考える。連続列の候補を何個か貪欲で選んでそれを遷移にするようなのを考える。
10:00 実装途中にとんでもない事実に気がつく。priority_queueの中身の順序がまずいので評価値順に並んでいないのとか評価値が低い方からk個選ぶようなとんでもないコードになっている。まともに直したらビームサーチ部分がやたら時間がかかるようになってビーム幅が2になった…
提出したら805260点で121位/224相当になる。目標の80万にとりあえず届いてよかった。
感想
とりあえず80万点は届いてよかった。ただ時間かけすぎだったり連続列をつくるべきなのに気づくのが遅すぎたり色々反省。ビームサーチとか手元にジャッジ環境つくるのとか何となくマラソンの雰囲気がわかったので色々やっていきたい。コードの管理がひどかったのでこれからはちゃんとgitで管理したい。
解説記事を読んで復習しようとしたがtopcoderのMMが始まってしまったのでそっちが一区切りついたら復習して追記するつもり。
ABC074 D Restoring Road Network
問題ページ
D - Restoring Road Network
考えたこと
問題を読むとワーシャルフロイドの逆をやるらしい。それぞれの頂点間にA[i][j]の長さの辺があるのを初期状態として、どの辺を減らせるかといった方針で考える。i->k->jと移動した時、A[i][j]と同じコストで移動できるならi->jへの辺はなくても問題ないはず。また、A[i][j]より小さいコストであれば前提がおかしいのでそのようなグラフは存在しない。 したがってO(N^3)で中間となる頂点kと2頂点i, jについて消せる辺を求めて残っている辺の長さが答えになると思って出したら通った。
//#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int a[305][305], dp[305][305]; signed main(void) { int n; cin >> n; REP(i, n) REP(j, n) cin >> a[i][j], dp[i][j] = a[i][j]; REP(k, n) REP(i, n) REP(j, n) { if(k == i || k == j || i == j || dp[i][k] == INF || dp[k][j] == INF) continue; if(dp[i][k] + dp[k][j] == a[i][j]) { dp[i][j] = INF; } else if(dp[i][k] + dp[k][j] < a[i][j]) { cout << -1 << endl; return 0; } } ll sum = 0; REP(i, n) REP(j, n) if(dp[i][j] != INF) sum += dp[i][j]; cout << sum/2 << endl; return 0; }
SRM616 div1 easy WakingUp
考えたこと
とりあえず周期性がありそう。全てのアラームが鳴るタイミングまで進めばあとは周期lcmで繰り返されそう。10以下の整数のlcmは5*7*8*9=2520で計算量的には問題なさそう。周期の部分が負なら必ず起きそうなので-1を返すことにする。サンプル3で全てのアラームが鳴るタイミングが求められない。よくよく考えるとそもそも鳴るタイミングの偶奇が一致しないパターンも存在するし全てのアラームが鳴るタイミングがないパターンがある。このあたりを例外処理したつもりの怪しいコードを書いて出してみる。案の定落ちる。
解説記事を読むとそもそも全てのアラームが鳴るタイミングまで進まなくても周期lcmの周期性があるらしい。言われてみれば自明。imosを使ってシミュレーションを書くと通った。
学び
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; ll gcd(ll a, ll b) { return b != 0 ? gcd(b, a%b) : a; } ll lcm(ll a, ll b) { return a/gcd(a, b)*b; } int imos[3010]; class WakingUp { public: int maxSleepiness(vector<int> p, vector<int> s, vector<int> v, int D) { int n = p.size(); memset(imos, 0, sizeof(imos)); REP(i, n) { int j=s[i]; while(j<2521) imos[j]-=v[i], j+=p[i]; } FOR(i, 1, 2521) imos[i] += D; FOR(i, 1, 2521) imos[i] += imos[i-1]; if(imos[2520] < 0) return -1; int ret = INF; FOR(i, 1, 2521) chmin(ret, imos[i]); if(ret >= 0) return 0; else return abs(ret); } };
SRM615 div1 easy AmebaDiv1
考えたこと
Xに含まれないサイズはそのサイズを初期サイズとすれば最終サイズも等しくなるので必ずSに含まれる。Xに含まれるサイズを全て試せばいい。
実装したら通った。ものすごい簡単で逆に驚いた。
// BEGIN CUT HERE // END CUT HERE //#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; map<int, bool> mp; class AmebaDiv1 { public: int count(vector <int> X) { int n = X.size(); REP(i, n) mp[X[i]] = false; for(auto i: mp) { int now = i.first; REP(j, n) { if(now == X[j]) now *= 2; } if(mp.find(now) != mp.end()) mp[now] = true; } int ret = 0; for(auto i: mp) if(!i.second) ret++; return ret; } };
