Codeforces Round #230 (Div.1) B. Tower of Hanoi
問題概要
ハノイの塔のパズルの最小手数は 2^n - 1 であることは有名な事実であるが，今回は以下の問題を考えるとする．
ある段を位置 i から位置 j に移すのにコストが t[i][j] かかるとするとき( 1 <= i, j <= 3 )，最初位置 0 にある n 段の塔を，位置 2 に移すときのトータルのコストを最小化せよ．手数は最小化しなくともよい．
・制約
1 <= n <= 40
解法
最小手数が 2^n - 1 である，ということの漸化式の証明が頭にあれば，すぐに dp の式を導けると思います．
dp[i][from][to] := i 段の塔を位置 from から to に移すときの最小コスト
とします．また，もう一つの位置を other とします．
dp[i][from][to] は，以下の2つのどちらかです．
- i - 1 段の塔を from から other に移す．その後，i 段目を from から to に移す．最後に i - 1 段の塔を other から to に移す．
- i - 1 段の塔を from から to に移す．次に i 段目を other に移す．その後 i - 1 段の塔をまた from に戻す．そして i 段目を other から to に移す．最後に i - 1 段の塔を from から to に移す．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int t[3][3] = {}; int n; for(int i = 0; i < 3; ++i) { for(int j = 0; j < 3; ++j) { cin >> t[i][j]; } } cin >> n; ll dp[41][3][3] = {}; for(int i = 1; i <= n; ++i) { for(int from = 0; from < 3; ++from) { for(int to = 0; to < 3; ++to) { int other = 3 - from - to; dp[i][from][to] = t[from][to] + dp[i - 1][from][other] + dp[i - 1][other][to]; ll tmp = 2 * dp[i - 1][from][to] + dp[i - 1][to][from] + t[from][other] + t[other][to]; dp[i][from][to] = min(dp[i][from][to], tmp); } } } cout << dp[n][0][2] << endl; }
AOJ 2611 Ordering
解法
問題文を丁寧に読まなければならない問題です．
「それぞれの塔は自分自身よりも大きな塔とは高々1回しか比較されていない」とあるので，与えられた関係 (a, b) を有向辺とみるとこれは木になっています．
この時点で木DPかなあという見通しが立ちます．
ある頂点のそれぞれの部分木は独立に考えることができるので，あとはそれらをいい感じにマージしていくことになります．
引き分けがなければ単純に挿入していくDPなんですが，今回は引き分けがあるのでうまく処理しなければなりません．
（高さの異なる塔を高さ順に並べていくイメージだとすると，引き分けは同じところに複数の塔を置くということになります．）
ここで以下のDPを考えます．
dp2[i][j][k] := 高さが異なる i 個の集合 A と，高さが異なる j 個の集合 B をマージして，最終的に高さが異なる k 個の集合にする場合の数
遷移は以下の通り，3通りあります．
- A の i 番目の塔が B の j 番目よりも高い => dp2[i - 1][j][k - 1]
- A の i 番目と B の j 番目の高さが等しい => dp2[i - 1][j - 1][k - 1]
- A の i 番目より B の j 番目のほうが高い => dp2[i][j - 1][k - 1]
dp2[i][j][k] はこれらの和になります．
このDPテーブルは前もって計算できるのでそうします．
あとはマージしていくだけで，これは難しくありません．以下のDPでできます．
dp[v][i] := 根が v の部分木で，高さが異なる塔が i 個あるような関係の作り方の総数
この dp テーブルを先程の dp2 を使って計算していきます．
今構築中の高さの関係を
tmp[i][j] := i 番目の子まで見たときに，高さが異なる塔が j 個であるような総数
とすると，
tmp[i + 1][l] += tmp[i][j] * dp[ch[i]][k] * dp2[j][k][l]
という式が書けるので，各 i, j, k, l についてループを回します．
各頂点でこれをやるので，ぱっと見た感じでは（ch の i は無視できるので）j, k, l の3重ループと合わせて O(N^4) っぽいですが，計算量の漸化式を書いてみると実は O(N^3) になっています．
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll M = 1e9 + 7; ll dp2[256][256][256]; int sz[256]; int dfs(int v, vector<vector<int>>& g, vector<vector<ll>>& dp) { if(g[v].size() == 0) { dp[v][1] = 1; return sz[v] = 1; } sz[v] = 1; for(auto ch : g[v]) { sz[v] += dfs(ch, g, dp); } vector<vector<ll>> tmp(g[v].size() + 1, vector<ll>(sum)); tmp[0][0] = 1; for(int i = 0; i < (int)g[v].size(); ++i) { int ch = g[v][i]; for(int l = 0; l < sz[v]; ++l) { for(int j = 0; j <= l; ++j) { for(int k = 1; k <= sz[ch]; ++k) { (tmp[i + 1][l] += (tmp[i][j] * dp[ch][k] % M) * dp2[j][k][l]) %= M; } } } } for(int i = 0; i < sum; ++i) { dp[v][i + 1] = tmp[g[v].size()][i]; } return sz[v]; } int main() { for(int i = 0; i < 201; ++i) { dp2[i][0][i] = 1; dp2[0][i][i] = 1; } for(int k = 1; k < 201; ++k) { for(int i = 1; i < 201; ++i) { for(int j = 1; j < 201; ++j) { (dp2[i][j][k] += dp2[i - 1][j - 1][k - 1] + dp2[i - 1][j][k - 1] + dp2[i][j - 1][k - 1]) %= M; } } } int N; cin >> N; vector<vector<int>> g(N); vector<bool> in(N); for(int i = 0; i < N - 1; ++i) { int a, b; cin >> a >> b; g[a].push_back(b); in[b] = true; } int root = -1; for(int i = 0; i < N; ++i) { if(!in[i]) { root = i; break; } } vector<vector<ll>> dp(N + 1, vector<ll>(N + 1)); dfs(root, g, dp); ll res = 0; for(int i = 0; i <= N; ++i) { (res += dp[root][i]) %= M; } cout << res << endl; }
感想
O(N^4) から落ちへんやんけ！と言いながらヤケクソで投げたら通り，計算量の見積もりが甘かったと気付かされた．
実はオーダーが落ちて（？）いるというのは，結構面白かったし今後も使えそうなので覚えておきたい．
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つまでは考えるけど，重複どうするかが辛くて答え見ちゃった．
この問題は個人的に結構面白かったです．
