ACPC2014 Day2 I Hard Beans
解法
WaveletMatrixで殴ると通ります．
具体的には，区間の何番目の値が D との大小関係の境界になっているか quantile で二分探索するだけです．
ソースコード
#include <bits/stdc++.h> using namespace std; // wavelet matrix が長すぎる int main() { int N; cin >> N; vector<int> a(N); for(int i = 0; i < N; ++i) { cin >> a[i]; } wavelet_matrix<int> wm(a); int Q; cin >> Q; while(Q--) { int l, r, D; cin >> l >> r >> D; int lb = 0, ub = r - l; while(ub - lb > 1) { int m = (ub + lb) / 2; if(wm.quantile(l, r + 1, m) >= D) { lb = m; } else { ub = m; } } cout << min(abs(wm.quantile(l, r + 1, lb) - D), abs(wm.quantile(l, r + 1, ub) - D)) << endl; } }
感想
想定解はなんだろう？流石にWaveletMatrixで殴れって問題じゃないはずだけども．
Codeforces Round #433 (Div. 2) D. Jury Meeting
問題概要
街が n + 1 あり，それぞれナンバリングされている．また人が n 人いて，人 i は街 i に存在する．0番目の街は首都であり，人はいない．
ここで，飛行機のスケジュールが m 個与えられる．スケジュールは以下のようになっている．
d[i] 日に出発してその日のうちに到着し，街 f[i] から 街 t[i] に行くが，これにはコストが c[i] かかる．また，f[i] == 0 または t[i] == 0 が必ず成り立つ．（どちらかは必ず首都である）
この時，n 人すべてが首都に同時に k 日間いるような期間が存在し，かつ自分の街まで帰るような飛行機の利用の仕方で，コストを最小化せよ．
・制約
1 <= n <= 10^5
0 <= m <= 10^5
1 <= k <= 10^6
1 <= d[i] <= 10^6
0 <= f[i], t[i] <= 10^6
1 <= c[i] <= 10^6
解法
最初に d[i] でスケジュールをソートしておきます．
まず，コストを無視して全員が最短で首都につくタイミングを lb，全員が自分の街まで帰ることができるギリギリを ub とします．（後者は，スケジュールを逆順に見れば良いです．）
lb と ub の日の差が k + 1 より小さければ，同時に k 日間滞在できません．
そうでない場合は，幅が k + 1 より小さくならないように，lb と ub をいい感じに伸ばしてやって，その中で一番良いものを選ぶことになります．
これはちょうどしゃくとりっぽい発想なので，それで実装します．
go[i] := i 番目の人が行きで使えるコストの集合 (multiset)
ret[i] := i 番目の人が帰りで使えるコストの集合 (multiset)
とし，伸ばすときは insert して，縮めるときは erase します．
値の更新は begin() の値を足し引きするだけなので，難しくはないです．
計算量は O(mlogm + n) ．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; constexpr int INF = 1e9; constexpr long double eps = 1e-8; struct flight { int d, f, t, c; bool operator<(flight const& f) const { return d < f.d; } }; int main() { int n, m, k; cin >> n >> m >> k; vector<flight> fs(m); for(int i = 0; i < m; ++i) { scanf("%d %d %d %d", &fs[i].d, &fs[i].f, &fs[i].t, &fs[i].c); } sort(begin(fs), end(fs)); vector<multiset<ll>> go(n + 1), ret(n + 1); set<int> gs, rs; int lb = -1, ub = -1; for(int i = 0; i < m; ++i) { if(fs[i].t == 0) { go[fs[i].f].insert(fs[i].c); gs.insert(fs[i].f); } if(gs.size() == n) { lb = i; break; } } for(int i = m - 1; i >= 0; --i) { if(fs[i].f == 0) { ret[fs[i].t].insert(fs[i].c); rs.insert(fs[i].t); } if(rs.size() == n) { ub = i; break; } } if(lb == -1 || ub == -1 || fs[ub].d - fs[lb].d < k + 1) { cout << -1 << endl; return 0; } int l = lb, r = ub; while(fs[ub].d - fs[l + 1].d >= k + 1) { if(fs[l + 1].t == 0) { go[fs[l + 1].f].insert(fs[l + 1].c); } l++; } ll t = 0; for(int i = 1; i <= n; ++i) { t += *go[i].begin() + *ret[i].begin(); } ll res = t; while(fs[r - 1].d - fs[lb].d >= k + 1) { r--; while(fs[r].d - fs[l].d < k + 1) { if(fs[l].t == 0) { t -= *go[fs[l].f].begin(); go[fs[l].f].erase(fs[l].c); t += *go[fs[l].f].begin(); } l--; } if(fs[r].f == 0) { t -= *ret[fs[r].t].begin(); ret[fs[r].t].insert(fs[r].c); t += *ret[fs[r].t].begin(); } res = min(res, t); } cout << res << endl; }
AOJ 2372 IkaNumber
解法
問題文を言い換えると，フィボナッチ数同士の積で表される数で K 番目に小さいものは何か？という問題です．
実験すればなんとなく規則性が見えてきます．
自分は fib(n) * fib(m) (1 <= n, m <= 10 ぐらい）の表を出力したらわかりました．
小さい順から斜めにずら～っとならんだ感じの表が得られます．
あとは何番目の斜めの場所にあるか探索して，いい感じにインデックスを合わせるだけです．
コーナーケースはないですが，ちゃんと手で確かめないとインデックスがずれやすいかも．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using matrix = vector<vector<ll>>; constexpr ll M = 1e9 + 7; matrix mul(matrix a, matrix b) { matrix res(a.size(), vector<ll>(b[0].size())); for(int i = 0; i < (int)a.size(); ++i) { for(int k = 0; k < (int)b.size(); ++k) { for(int j = 0; j < (int)b[0].size(); ++j) { (res[i][j] += a[i][k] * b[k][j]) %= M; } } } return res; } matrix modpow(matrix x, ll n) { matrix res(x.size(), vector<ll>(x.size())); for(int i = 0; i < (int)x.size(); ++i) { res[i][i] = 1; } while(n > 0) { if(n & 1) { res = mul(res, x); } x = mul(x, x); n >>= 1; } return res; } ll fib(int n) { matrix A(2, vector<ll>(2)); A[0][0] = A[0][1] = 1; A[1][0] = 1; matrix b(2, vector<ll>(1)); b[0][0] = b[1][0] = 1; return mul(modpow(A, n - 1), b)[0][0]; } int main() { ll K; cin >> K; ll lb = 0, ub = 1e10; while(ub - lb > 1) { ll m = (lb + ub) / 2; if(m * (m + 1) < K) { lb = m; } else { ub = m; } } K -= lb * (lb + 1); int x = lb * 2 + (K - 1) / ub + 1; if(K > ub) { K -= ub; } int y = 0; if(K <= (ub + 1) / 2) { y = 2 * K - 1; } else { y = ub - (ub & 1) - (K - (ub + 1) / 2 - 1) * 2; } cout << (fib(y) * fib(x - y + 1) % M) << endl; }
感想
実験は大切だと再認識する問題．
これは一般的な話ですが，闇雲に実験しても（無駄ではないですが）いい知見が得られないことも多くて，実験するのにも経験が必要だなあと感じます．
AOJ 2159 Symmetry
問題概要
点が N 個与えられる．これらすべての点で，自己交差しないように辺を結ぶことで線対称な多角形を構成できるか判定せよ．
ただし，点は多角形の順番（反時計回り or 時計回り）であたえられるわけではない．
・制約
1 <= N <= 1000
解法
適当に2点を決めて，それの垂直二等分線を軸の候補とすると，全体で O(N^3) かかってしまうので間に合いません．
しかしよく考えると，凸包を作って，隣接する2点の垂直二等分線または向かい合う点同士を結んだ直線だけを候補として良いことがわかります．
これは自分で図を書いてみたほうがわかりやすいと思います．（線対称な凸でない多角形を書いてみて，その線と凸包を比べるとわかります．）
あとは線を引いた後に対称か判定するだけなんですが，小数点上で計算をするので，最終的に各点の座標を int に戻してやって，点の set の上で対称な位置に点があるかどうか見ればいいです．
コーナーケースは一直線上に点が並んでいるときで，最初にチェックしておきます．
ソースコード
#include <bits/stdc++.h> using namespace std; using ld = long double; constexpr ld eps = 1e-8; constexpr ld pi = std::acos(-1.0); using pii = pair<int, int>; // ライブラリは長いので略． int main() { int N; cin >> N; set<pii> ps; polygon poly; double gx = 0, gy = 0; for(int i = 0; i < N; ++i) { int x, y; cin >> x >> y; gx += x; gy += y; ps.insert(make_pair(x, y)); poly.emplace_back(x, y); } bool ok = false; // 一直線上に並んでいればNG for(int i = 2; i < N; ++i) { if(abs(cross(poly[1] - poly[i], poly[0] - poly[i])) > eps) { ok = true; } } if(!ok) { cout << "No" << endl; return 0; } sort(poly.begin(), poly.end(), [gx, gy](auto const& p1, auto const& p2) { return arg(p1 - point(gx, gy)) < arg(p2 - point(gx, gy)); }); poly = convex_hull(poly); vector<line> ls; int const m = poly.size(); for(int i = 0; i < (int)poly.size(); ++i) { ls.emplace_back(poly[i], poly[i + m / 2]); ls.emplace_back(separate(poly[i], poly[(i + 1) % m])); } for(auto& l : ls) { ok = true; int on_line = 0; for(auto& p : ps) { auto ref = reflection(l, point(p.first, p.second)); auto x = real(ref), y = imag(ref); if(abs(x - round(x)) > eps || abs(y - round(y)) > eps) { ok = false; break; } int ix = round(x), iy = round(y); if(ps.count(make_pair(ix, iy)) == 0) { ok = false; break; } on_line += make_pair(ix, iy) == p; } if(ok && on_line <= 2) { cout << "Yes" << endl; return 0; } } cout << "No" << endl; }
Typical DP Contest Q - 連結
解法
同じ文字列を複数選んでも良いので，何を使ったかを保存する必要はないです．
今作っている文字列の状態がどうか，がわかれば十分．
そこで突然ですが，以下のような dp をします．
dp[i][j][k] := 文字列が i 文字目まで出来ているとき，直近 7 文字が j で，単語の区切り位置としてありえるのが k であるような場合の数
この DP において，今できている文字列から次の新しい文字列を作る時，単語単位で追加していくのではなく，文字単位(0 or 1)で追加していくと，自然に単語間の重複を防ぐことができます．
さて，1文字追加したあとに，単語の区切りの位置としてあり得る位置から末尾までの文字列と等しい文字列が単語の中に含まれていれば，末尾も区切り位置としてあり得る位置になります．
求める答えは，きちんと単語列で表現できるものなので，dp[L][i][末尾が区切り位置になっているもの] の総和です．
（末尾が区切り位置になっている <-> 最下位のビットが 1 である）
実装に関しては，直近7文字と，区切り位置の8箇所分はビットで持ちます．
1文字追加は左シフトで，末尾の情報を OR で追加してやると良いです．
どうしてこれで重複カウントされないかという大雑把な説明をします．
そもそもどうして重複カウントが起こるのかというと，例えば "0011"，"00"，"11"という単語があったときに，"0011" を作るパターンが2通りあり，これは単語ごとに追加する遷移では区別するのが難しいということに起因します．
上の状態で表現するなら，空文字の状態から "0011 |"が作れてしまうし，"00 |"の状態から"00 | 11 |" が作れてしまって，これらが別にカウントされてしまうということです．
しかし一文字ずつ遷移し，区切り位置を保存しておくDPにおいては，"0011"という文字列は必ず "00 | 11 |" というパターンにマッチして，"0011 |"というパターンにはマッチしません．これは遷移を考えればあきらかにわかることです．
（"0" に '0' を追加するときに，必ず次状態は "00 |" になるから．）
以下例．
w = {"01", "10", "11"}
今 "010" まで出来ているとすると，区切り位置としてありえるのは "01 | 0" の1箇所だけ．
ここに 1 を追加しようとすると，"01 | 01"になる．"01" は単語列にあるので，次の状態は "01 | 01 |" になる．
0 を追加しようとすると，"01 | 00" になるが，"00" は単語列にないので，次の状態は "01 | 00" になる．
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int M = 1e9 + 7; int main() { int N, L; cin >> N >> L; vector<vector<int>> w(16, vector<int>(1 << 8)); for(int i = 0; i < N; ++i) { string s; cin >> s; int b = 0; for(int j = 0; j < (int)s.size(); ++j) { b |= (s[j] - '0') << j; } w[s.size()][b] = 1; } vector<vector<vector<int>>> dp(128, vector<vector<int>>(1 << 7, vector<int>(1 << 8))); dp[0][0][1] = 1; for(int i = 0; i < L; ++i) { for(int j = 0; j < 1 << 7; ++j) { // 直前の 7 文字 for(int k = 0; k < 1 << 8; ++k) { // 区切りの位置 for(int l = 0; l < 2; ++l) { // 次に追加する文字 0 or 1 int f = 0; // 次に l を追加したとき，ある接尾辞に対応する単語があるか？ for(int m = 0; m < 8; ++m) { int b = ((j << 1) | l) & ((1 << (m + 1)) - 1); if(k >> m & 1 && w[m + 1][b]) { // 位置 k で区切った後ろの文字列に対応する w がある f = 1; // 区切り位置として末尾が増える } } int nj = (j << 1) & 127 | l; int nk = (k << 1) & 255 | f; (dp[i + 1][nj][nk] += dp[i][j][k]) %= M; } } } } int res = 0; for(int i = 0; i < 1 << 7; ++i) { for(int j = 0; j < 1 << 7; ++j) { (res += dp[L][i][(j << 1) + 1]) %= M; } } cout << res << endl; }
感想
直前の7文字まで持てば十分 <- これは自然な発想
区切りの位置を持つ <- 文字列を単語のブロックに分けて表現したいという発想なので，まあ自然
1文字ずつ見れば重複も避けられるよね <- これが一番気づきにくくて，一番大切なところかな？
最初の2つまでは考えるけど，重複どうするかが辛くて答え見ちゃった．
この問題は個人的に結構面白かったです．
AOJ 2336 Spring Tiles
解法
最適な戦略を取った場合，各マスの移動は確率的に決まるわけではなく，ある基準によってバネに向かうかゴールに直接向かうか定まっているはずです．
問題はなにが基準なのかですが，これは自然に「今いる地点がバネとゴールのどちらにどれぐらい近いか」であるとわかります．
なので，バネを根とする幅優先探索（ゴールを壁とみなす）と，ゴールを根とする幅優先探索（バネを壁とみなす）が必要です．
また，これも大切なことですが，すべてのバネは同一に扱えます．つまり，バネを使ってからゴールに着く期待値を E とすると，これはどのバネでも同じであるということです．
よって以下の式が成り立ちます．
$\displaystyle E = \frac{\sum_{s \in S}gd[s] + \sum_{t \in T}(sd[t] + E)}{H \times W}$
ただし，$S$は直接ゴールに向かうのが最適なマスの集合，$T$はバネに向かうのが最適な集合です．また，$gd$と$sd$はそれぞれゴールからの距離とバネからの距離を表します．
$E$の項を左辺に移行して変形すると，Eの値が求まります．
$S$ と $T$ の集合を決めるのに先程の基準を使いますが，初期状態をとりあえずすべてのマスが $S$ であると定めて，すこしずつ $T$ にうつしていけば良いです．
基準の値は，愚直に -H*W から H*W まで全通り試しても十分間に合います．
sd[i] - gd[i] の値が基準値を下回ったら，そのマスはバネに向かうとして，先の式の各値を更新し，そのたびに E を再計算します．（こういうことをするためには，sd[i] - gd[i] の値をソートしておく必要があります．）
E が求まったら，始点が現在の最適戦略でバネに向かうかゴールに向かうか確認して，前者なら sd[start] + E が，後者なら gd[start] が候補になります．
注意するべき点は，壁などの存在により，そもそもバネにしか行けないマス，どちらにも行けないマス，ゴールにしか迎えないマスを，最初から S と T に決め打ちして入れてしまう必要があるところです．
計算量は，ソートが一番重くて O(HWlogHW) です．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; constexpr int INF = 1e9; constexpr int dx[4] = {0, 1, 0, -1}; constexpr int dy[4] = {1, 0, -1, 0}; int main() { int W, H; cin >> W >> H; vector<string> v(H); int s, g; int fcnt = 0; queue<int> que; vector<int> sd(H * W, INF); for(int i = 0; i < H; ++i) { cin >> v[i]; for(int j = 0; j < W; ++j) { if(v[i][j] == 's') { s = i * W + j; } else if(v[i][j] == 'g') { g = i * W + j; } else if(v[i][j] == '*') { que.push(i * W + j); sd[i * W + j] = 0; } fcnt += v[i][j] == '.' || v[i][j] == 's'; } } while(!que.empty()) { int y = que.front() / W; int x = que.front() % W; que.pop(); for(int i = 0; i < 4; ++i) { int ny = y + dy[i]; int nx = x + dx[i]; if(ny < 0 || H <= ny || nx < 0 || W <= nx || v[ny][nx] == '#' || v[ny][nx] == 'g' || sd[ny * W + nx] != INF) { continue; } sd[ny * W + nx] = sd[y * W + x] + 1; que.push(ny * W + nx); } } vector<int> gd(H * W, INF); que.push(g); gd[g] = 0; double total_gd = 0; while(!que.empty()) { int y = que.front() / W; int x = que.front() % W; que.pop(); for(int i = 0; i < 4; ++i) { int ny = y + dy[i]; int nx = x + dx[i]; if(ny < 0 || H <= ny || nx < 0 || W <= nx || v[ny][nx] == '#' || v[ny][nx] == '*' || gd[ny * W + nx] != INF) { continue; } gd[ny * W + nx] = gd[y * W + x] + 1; total_gd += gd[ny * W + nx]; que.push(ny * W + nx); } } vector<pll> d; int scnt = 0; double total_sd = 0; for(int i = 0; i < H * W; ++i) { if(i == g || v[i / W][i % W] == '*' || v[i / W][i % W] == '#') { continue; } if(gd[i] == INF && sd[i] != INF) { scnt++; total_sd += sd[i]; } else if(sd[i] != INF) { d.emplace_back(-gd[i] + sd[i], i); } } sort(d.begin(), d.end()); double res = 1e18; auto it = d.begin(); for(int i = -H * W; i <= H * W; ++i) { while(it != end(d) && it->first <= i) { scnt++; total_sd += sd[it->second]; total_gd -= gd[it->second]; it++; } if(scnt == fcnt) { continue; } double E = (total_gd + total_sd) / (1 - (double)scnt / fcnt) / fcnt; if(gd[s] == INF || -gd[s] + sd[s] <= i) { res = min(res, E + sd[s]); } else { res = min(res, (double)gd[s]); } } cout << fixed << setprecision(10) << res << endl; }
感想
なんとなくいい問題だと思った．
解いてから他の人の解法読んだりしたんですが，double を使って誤差で死んだという人が結構いるらしい．
自分は何も考えずに double で通っちゃったんだけど，実装方針によるのかな？
Typical DP Contest R - グラフ
解法
どう考えても閉路は一つにまとめたいな～という気持ちになるので，とりあえずSCCしたあとのDAGの上で解くことを考えます．
一番端っこから引いていくのが当然良いので，トポロジカルソートしてその順番にDPしていくことを考えます．
2本引いていくため，以下のようなDPでうまく状態を持ちます．
dp[i][j] := 最後に伸ばした辺の先が i で，もう一方の端が j であるときの最大
このとき，j がトポロジカル順序で i を越えないようにもっておくことで，同じ頂点をカウントせずに済ませることができます．
遷移は，i から伸ばすか j から伸ばすかで2通りあります．（伸ばそうとする先は i よりトポロジカル順序があとの頂点．）
i から伸ばすのは自由なので普通に伸ばします．
j から伸ばすときは，重複カウントを避けるために i を飛び越えて伸ばさなければなりません．あらかじめ j から（いくつかの頂点を辿って）k にいけるかどうかを計算しておくと実現できます．
サイズ0のダミーの頂点をトポロジカル順序で一番最初にくるように入れておくと，一番最初の頂点を選ぶ操作をさっきの遷移で自然に実現できるので楽です．
この頂点は他のすべての頂点にいけるようにしておきます（逆は行けない）．
max(dp[i][j]) が答えになります．
ソースコード
#include <bits/stdc++.h> using namespace std; using graph = std::vector<std::vector<int>>; // SCC と tsort は略 int main() { int N; cin >> N; graph gg(N, vector<int>(N)); for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) { cin >> gg[i][j]; } } vector<int> cmp(N); int const K = scc(gg, cmp); auto g = build_graph(gg, cmp, K); vector<int> sz(K + 1); for(int i = 0; i < N; ++i) { sz[cmp[i]]++; } auto topo = tsort(g); // トポロジカルソートする topo.insert(topo.begin(), K); // ダミーの頂点 // いくつかの頂点と通って行けるかどうか vector<vector<bool>> can(K + 1, vector<bool>(K + 1)); for(int i = 0; i < K; ++i) { can[K][i] = 1; } for(int i = 0; i < K; ++i) { for(int j = 0; j < K; ++j) { can[i][j] = g[i][j]; } } for(int k = 0; k < K + 1; ++k) { for(int i = 0; i < K + 1; ++i) { for(int j = 0; j < K + 1; ++j) { can[i][j] = can[i][j] | can[i][k] & can[k][j]; } } } vector<vector<int>> dp(K + 1, vector<int>(K + 1)); for(int i = 0; i < K + 1; ++i) { for(int j = 0; j < i; ++j) { int u = topo[i], v = topo[j]; dp[u][v] = max(dp[u][v], sz[u] + sz[v]); for(int k = i + 1; k < K + 1; ++k) { int w = topo[k]; if(can[u][w]) { dp[w][v] = max(dp[w][v], dp[u][v] + sz[w]); } if(can[v][w]) { dp[w][u] = max(dp[w][u], dp[u][v] + sz[w]); } } } } int res = 0; for(int i = 0; i < K + 1; ++i) { for(int j = 0; j < K + 1; ++j) { res = max(res, dp[i][j]); } } cout << res << endl; }
感想
SCCとかトポロジカル順序の発想は自然だし，遷移はかなりわかりやすいし，コードも別にややこしくないけど，DPテーブルの持ち方考えるのは結構つらいと思った．
これが簡単だと思える人はどんな訓練を積んできたんですかね……？
