Tenka1 Programmer Contest D - IntegerotS
問題ページ
D - IntegerotS
考えたこと
ナップザック問題っぽさを感じる。Kをそのまま配列に持つのは無理なのでbitが立ってる本数を配列に持つのかなあと考えるがうまくいきそうにない。
いろいろ実験してるとKのある桁を1から0にしたとき、それ以下の桁は全て1にするべきなことに気づく。取る数字のorを全て取ったものをXとすると、Xは高々30通りしか存在せず、O(n)で各Xについて最善な取り方が求まるので計算量的に問題ない。
#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[100010], b[100010]; signed main(void) { int n, k; cin >> n >> k; REP(i, n) cin >> a[i] >> b[i]; int ret = 0; REP(j, n) { bool flag = true; REP(l, 30) { if((a[j]>>l)&1 && !((k>>l)&1)) {flag = false; break;} } if(flag) ret += b[j]; } int ans = ret; REP(i, 30) { // kの上位ibit目が1 → そこを0にしてそこより下位のbitを1に if(k>>i&1) { int c = k&~(1LL<<i); c |= (1LL<<i)-1; // a[j]でbitが立っていてcでbitが立っていない → だめ int ret = 0; REP(j, n) { bool flag = true; REP(l, 30) { if((a[j]>>l)&1 && !((c>>l)&1)) {flag = false; break;} } if(flag) ret += b[j]; } chmax(ans, ret); } } cout << ans << endl; return 0; }
Tenka1 Programmer Contest E - CARtesian Coodinate
問題ページ
E - CARtesian Coodinate
解法
解説を見た。
https://img.atcoder.jp/tenka1-2017/editorial.pdf
www.youtube.com
まず、N点からのマンハッタン距離の和が最小になる点について考える。マンハッタン距離はx座標、y座標それぞれ独立に足すことができるのx方向とy方向でそれぞれ独立に考えることができる。また、距離の和が最小になる点は中央値になる。中央値から右にΔt動かしたとすると(右の頂点の数)Δtの分距離の総和が減るが、(左の頂点の数)Δtの分距離の総和が増えるため総和が減ることはありえない。左に動かすのも同様。よって中央値から動かして得になるケースは絶対に存在しない。
(Δt*2減るがΔt*3増えるので得しない)
よって、交点の座標の中央値を求めることができれば解ける。交点はO(N^2)個存在するので愚直に全列挙するのは間に合わない(はず)。二分探索することを考えると座標sより左側にある交点を高速に列挙できれば二分探索が可能。
座標sの地点で直線が並ぶ順番と左側に交点が存在しない十分左の座標で直線が並ぶ順番はそれぞれO(N)で求めることができる。このとき、交点は順番が入れ替わっている直線の数となり、これは転倒数となる。
転倒数はBITを用いてO(NlogN)で求めることができるので二分探索の判定部分はO(NlogN)で可能。したがって求めることができる。
学び
マンハッタン距離の総和は次元ごとに独立に考えられる。総和が最小になる地点は中央値。
直線の交点の数は転倒数に帰着できる。
#include <bits/stdc++.h> using namespace std; typedef long long ll; // #define int 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 #ifdef int const int INF = (1LL<<30); #else const ll INF = (1LL<<60); #endif const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; 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 n; int a[40010], b[40010], c[40010]; pair<double, int> p[40010], p2[40010], p3[40010]; ll con; int bit[40010], m = 40010; //0からi-1番目までの和 int sum(int i) { i++; int s = 0; while(i > 0) { s += bit[i]; i -= i&-i; } return s; } //i番目(0-index)にxを加える void add(int i, int x) { i++; while(i <= m) { bit[i] += x; i += i&-i; } } bool check(double mid) { // 数列を求める // 画像と数列の並べ方が反対になってる REP(i, n) { int idx = p[i].second; p2[i] = {-(double)a[idx]/b[idx]*mid+(double)c[idx]/b[idx], i}; } sort(p2, p2+n); // p2.secondの転倒数を求める memset(bit, 0, sizeof(bit)); ll ans = 0; REP(i, n) { ans += i - sum(p2[i].second); add(p2[i].second, 1); } return ans >= con; } bool check2(double mid) { // 数列を求める REP(i, n) { int idx = p3[i].second; p2[i] = {-(double)b[idx]/a[idx]*mid+(double)c[idx]/a[idx], i}; } sort(p2, p2+n); // p2.secondの転倒数を求める memset(bit, 0, sizeof(bit)); ll ans = 0; REP(i, n) { ans += i - sum(p2[i].second); add(p2[i].second, 1); } return ans >= con; } signed main(void) { cin >> n; REP(i, n) { cin >> a[i] >> b[i] >> c[i]; p[i] = {-(double)a[i]/b[i], i}; p3[i] = {(double)b[i]/a[i]*INF+(double)c[i]/a[i], i}; } sort(p, p+n); sort(p3, p3+n); reverse(p, p+n); // 中央値はcon番目 con = n*(n-1)/4 + !!(n*(n-1)%4); // x座標 // 小数の二分探索は定数回で固定して回す double low = -1e10, high = 1e10; REP(_, 300) { double mid = (low+high)/2; if(check(mid)) { high = mid; } else { low = mid; } } cout << fixed << setprecision(15) << low << " "; // y座標 low = -1e10, high = 1e10; REP(_, 300) { double mid = (low+high)/2; if(check2(mid)) { high = mid; } else { low = mid; } } cout << low << endl; return 0; }
ARC039 C - 幼稚園児高橋君
問題ページ
C: 幼稚園児高橋君 - AtCoder Regular Contest 039 | AtCoder
考えたこと
解説を見た。
4方向の近傍だけ持ってればよくて通ったところとその近傍しか情報いらないからmapでうまく持てばO(KlogK)で解ける。linked listを思い出しつつバグらせないように気をつけながら実装をすると通った。
//#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[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1}; // x, y, dir の 最近傍の未訪問座標 // dir 0,右 1,下 2,左 3,上 map<VI, PII> mp; void update(int x, int y) { // (x, y)から右下左上への接続をする REP(i, 4) { // 存在しないなら生成 if(mp.find({x, y, (int)i}) == mp.end()) { mp[{x, y, (int)i}] = {x+dx[i], y+dy[i]}; } } // (x, y)の近傍から(x, y)への接続 // 右の左 = 左 PII p = mp[{x, y, 0}]; mp[{p.first, p.second, 2}] = mp[{x, y, 2}]; // 左の右 = 右 p = mp[{x, y, 2}]; mp[{p.first, p.second, 0}] = mp[{x, y, 0}]; // 上の下 = 下 p = mp[{x, y, 3}]; mp[{p.first, p.second, 1}] = mp[{x, y, 1}]; // 下の上 = 上 p = mp[{x, y, 1}]; mp[{p.first, p.second, 3}] = mp[{x, y, 3}]; } signed main(void) { int n; string s; cin >> n >> s; update(0, 0); int x = 0, y = 0; REP(i, n) { if(s[i] == 'R') { PII p = mp[{x, y, 0}]; x = p.first, y = p.second; update(p.first, p.second); } else if(s[i] == 'D') { PII p = mp[{x, y, 1}]; x = p.first, y = p.second; update(p.first, p.second); } else if(s[i] == 'L') { PII p = mp[{x, y, 2}]; x = p.first, y = p.second; update(p.first, p.second); } else if(s[i] == 'U') { PII p = mp[{x, y, 3}]; x = p.first, y = p.second; update(p.first, p.second); } } cout << x << " " << y << endl; return 0; }
AOJ 2429 marukaite
問題ページ
marukaite | Aizu Online Judge
考えたこと
解説を見た。
最小費用流を流すところは書けたが操作の復元に手間取った…最小費用流を行ったあと、容量が0の辺が存在すればその辺には流れたといえる。つまりR_iからC_jへの辺の容量が0であれば(i, j)は最終的に'o'であるといえる。よって最初の盤面と最終的な盤面を比較して異なる座標に操作を行ったといえる。
//#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}; #define MAX_V 10000 struct edge { int to, cap, cost, rev; }; int V; vector<edge> G[MAX_V]; int dist[MAX_V], prevv[MAX_V], preve[MAX_V]; void add_edge(int from, int to, int cap, int cost) { G[from].PB({to, cap, cost, (int)G[to].size()}); G[to].PB({from, 0, -cost, (int)G[from].size()-1}); } int min_cost_flow(int s, int t, int f) { int res = 0; while(f > 0) { fill(dist, dist+V, INF); dist[s] = 0; bool update = true; while(update) { update = false; REP(v, V) { if(dist[v] == INF) continue; REP(i, G[v].size()) { edge &e = G[v][i]; if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) { dist[e.to] = dist[v] + e.cost; prevv[e.to] = v; preve[e.to] = i; update = true; } } } } if(dist[t] == INF) return -1; int d = f; for(int v = t; v != s; v = prevv[v]) { chmin(d, G[prevv[v]][preve[v]].cap); } f -= d; res += d * dist[t]; for(int v = t; v != s; v = prevv[v]) { edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } int w[105][105], e[105][105]; string s[105], t[105]; signed main(void) { int n; cin >> n; REP(i, n) REP(j, n) cin >> w[i][j]; REP(i, n) REP(j, n) cin >> e[i][j]; REP(i, n) cin >> s[i]; REP(i, n) t[i] = string(n, '.'); // 'o'の位置のeraseコストの和を求める int sum = 0; REP(i, n) REP(j, n) if(s[i][j] == 'o') sum += e[i][j]; // supersource:0, supersink:1, 行:2からn+1, 列:n+2から2*n+1 V = 2*n+2; REP(i, n) add_edge(0, i+2, 1, 0); REP(i, n) add_edge(n+2+i, 1, 1, 0); REP(i, n) REP(j, n) { if(s[i][j] == 'o') { add_edge(i+2, j+n+2, 1, -e[i][j]); } else { add_edge(i+2, j+n+2, 1, w[i][j]); } } cout << sum + min_cost_flow(0, 1, n) << endl; // capが0の辺は使用している→最終盤面で'o' FOR(i, 2, n+2) for(edge e: G[i]) { if(e.cap == 0 && n+2 <= e.to && e.to < 2*n+2) { t[i-2][e.to-n-2] = 'o'; } } // 最初の盤面から変化していればその座標は操作している vector<PII> ans; REP(i, n) REP(j, n) { if(s[i][j] == t[i][j]) continue; ans.PB({i, j}); } cout << ans.size() << endl; for(auto i: ans) { cout << i.first+1 << " " << i.second+1; if(s[i.first][i.second] == '.') { cout << " write" << endl; } else { cout << " erase" << endl; } } return 0; }
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合宿を終えました。お疲れ様です。
