AOJ 2646 - Tournament
解法
全探索を考えるところから。
n が小さくで列を愚直に持てるとしたら、次の全探索を考えるはず。
res(l, r, rank) := 区間 [l, r) における勝者の最終順位が rank になるときの最適解
遷移は、m = (l + r) / 2, d = この区間の最終決戦の高さ（真の決勝からの高さ）として
res(l, r, rank) = min(res(l, m, rank) + res(m, r, d + 1), res(l, m, d + 1) + res(m, r, rank))
となる。
メモ化してもこのままだと間に合わない…
と思いきや、この探索は別に数列を愚直に持たなくてもできる。
今見ている区間が、ある区間 [a[i], a[i + 1]) に完全に内包されるなら、その瞬間に O(1) で計算できるからである。
このとき、メモ化するのは、rank == d のときだけでOK。
遷移を考えればわかるが、d == rank のときをメモ化しておけば、決勝からの高さ d のところで d != rank となるような探索は全体では d 回しか起こらない（はず、厳密に示してない）。
探索ノード数は、各区間 [a[i], a[i + 1])に対して、2べきサイズでごっそりとっていくイメージ（セグツリと似てる）なので、それぞれ log ぐらいのサイズ (n 以下) しかない。
なので、どんなに悪く見積もっても O(n^2 m) で解けている。
以下は map 使ってるので余計な log が付いてる。
定数倍厳しいときは気をつけないと普通に TLE しそう。
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int main() { int n, m; cin >> n >> m; vector<int> a(m + 1), b(m); for(auto& x : a) cin >> x; for(auto& x : b) cin >> x; vector<map<pii, int>> dp(n + 1); // consider ['l', 'r'), 'd' is depth, 'final_rank' represents this block winner's rank (2^r) function<int(int, int, int, int)> solve = [&] (int l, int r, int d, int final_rank) { if(final_rank == d && dp[final_rank].count({l, r})) return dp[final_rank][{l, r}]; const int i = lower_bound(begin(a), end(a), r) - begin(a) - 1; int res = 0; if(0 <= i && a[i] <= l && r <= a[i + 1]) { // contain completely if(b[i] >= d + 1) { res = r - l - (r - l) / (1 << (n - b[i] + 1)); } else { res = r - l - (b[i] == final_rank); } } else { // choose which block win const int mid = (l + r) / 2; res = min(solve(l, mid, d + 1, final_rank) + solve(mid, r, d + 1, d + 1), solve(l, mid, d + 1, d + 1) + solve(mid, r, d + 1, final_rank)); } if(final_rank == d) return dp[final_rank][{l, r}] = res; else return res; }; cout << solve(0, 1 << n, 0, 0) << endl; }
感想
なんか頭いいやり方があるのかと思って無限に悩んだ。
結局ただのメモ化再帰なんだなあ。ただ計算量解析が怪しい。
AOJ 2786 - Share the Ruins Preservation
解法
Andrew's Monotone Chain を左右からやっていくだけ。
有名な（？）蟻本の実装だと多角形の表現にするために半時計回りにやっているけど、今回はそんなことせずに、上側も下側も左からやっていけばいい。
左から/右から + 上側/下側 で4通りあるけど反転とかすると全部まとめられて若干サボれる（自分は左右しかサボってないけど）。
x 座標が同じ点では左右に分割できないことに注意する。
計算量は O(nlogn)
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using point = std::complex<ld>; constexpr ld eps = 1e-10; const ld pi = std::acos(-1.0); bool comp(point a, point b) { return std::real(a) < std::real(b) || (std::real(a) <= std::real(b) && std::imag(a) < std::imag(b)); } ld dot(point const& a, point const& b) { return std::real(std::conj(a) * b); } ld cross(point const& a, point const& b) { return std::imag(std::conj(a) * b); } int ccw(point a, point b, point c) { b -= a; c -= a; if(cross(b, c) > eps) return 1; if(cross(b, c) < -eps) return -1; if(dot(b, c) < 0) return 2; if(std::norm(b) < std::norm(c)) return -2; return 0; } ld triangle_area(point a, point b, point c) { return 0.5 * abs(cross(b - a, c - a)); } vector<ld> calc_area(vector<point> const& ps, bool rev = false) { vector<ld> S(ps.size()); vector<point> upper = {ps[0]}, lower = {ps[0]}; for(int i = 1; i < (int)ps.size(); ++i) { S[i] = S[i - 1]; while(upper.size() >= 2u && ccw(upper[upper.size() - 2], upper.back(), ps[i]) == 1) { S[i] -= triangle_area(upper[upper.size() - 2], upper.back(), lower.back()); upper.pop_back(); } while(lower.size() >= 2u && ccw(lower[lower.size() - 2], lower.back(), ps[i]) == -1) { S[i] -= triangle_area(lower[lower.size() - 2], lower.back(), upper.back()); lower.pop_back(); } S[i] += triangle_area(upper.back(), lower.back(), ps[i]); upper.push_back(ps[i]); lower.push_back(ps[i]); } if(rev) reverse(begin(S), end(S)); return S; } int main() { int n; cin >> n; vector<point> ps, rps; for(int i = 0; i < n; ++i) { int x, y; cin >> x >> y; ps.emplace_back(x, y); rps.emplace_back(-x, y); } sort(begin(ps), end(ps), comp); sort(begin(rps), end(rps), comp); const auto lS = calc_area(ps), rS = calc_area(rps, true); ll ans = rS[0]; for(int i = 0; i + 1 < n; ++i) { if(ps[i + 1].real() - ps[i].real() < eps) continue; ans = min(ans, (ll)roundl(lS[i] + rS[i + 1])); } cout << ans << endl; }
感想
凸法の基本練習にいいかも。
AOJ 2690 - Content Delivery
解法
各頂点について一番遠いところを貪欲に選ぶだけ。
一番遠いところへのパス以外はそこで切って、vector かなんかに突っ込んでおけばよい。
m がでかいけどどう考えても n^2 のオーダーで収まるので関係なし。
最後のソートがネックで O(n^2logn)
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct edge { int to; ll cost; edge(int t, ll c) : to(t), cost(c) {} }; using graph = vector<vector<edge>>; int main() { int n, m; cin >> n >> m; graph g(n); for(int i = 0; i < n - 1; ++i) { int a, b, c; cin >> a >> b >> c; g[a - 1].emplace_back(b - 1, c); g[b - 1].emplace_back(a - 1, c); } vector<ll> s(n); for(auto& ss : s) cin >> ss; vector<ll> cs; function<ll(int, int, ll)> dfs = [&] (int v, int p, ll st) { if(p != -1 && g[v].size() == 1u) return 0LL; // leaf vector<ll> ch; for(auto const& e : g[v]) { if(e.to == p) continue; ch.push_back(dfs(e.to, v, st) + st * e.cost); } const int idx = max_element(begin(ch), end(ch)) - begin(ch); for(int i = 0; i < (int)ch.size(); ++i) { if(i == idx) continue; cs.push_back(ch[i]); } if(p == -1) { // root cs.push_back(ch[idx]); } return ch[idx]; }; for(int i = 0; i < n; ++i) { dfs(i, -1, s[i]); } sort(begin(cs), end(cs), greater<>{}); cout << accumulate(begin(cs), begin(cs) + min((int)cs.size(), m), 0LL) << endl; }
感想
簡単すぎ。
AOJ 2743 - Land Inheritance
解法
全探索をちょっとだけ早くするだけ。
n <= 3 以下は土地を n 人で全部使い切るのが最適だから、ひっかかるところがないだろう。
n == 4 のときは、土地を使い切らない方法で最適なものがありうる。
具体的には螺旋っぽく配置するというもの。真ん中がぽっかり開いてるやつ。
分割する y 座標2箇所を決めると、上と下は（ある程度）独立に計算できる。
分割する y 座標2箇所が等しい場合はそれぞれで max とって2つの min で良い。
そうじゃないときは overlap しないように x 座標について一方がもう一方を超えないように計算する必要がある。
これは累積 max をとっておけば可能。
分割する y 座標の位置関係によってどっちが左側かが2パターンあるが、累積 max 取る前に swap してやると実装がサボれる。
実装の上では、m 人で領域 (y1, x1, y2, x2) を最適に分割する、という関数を作ると、各 n に対して全く同様の処理でかけて楽。
M = max(h, w) として O(M^3) で解ける。
ソースコード
#include <bits/stdc++.h> using namespace std; int solve(int y1, int x1, int y2, int x2, int num, vector<vector<int>> const& sum) { auto calc = [&sum] (int yy1, int xx1, int yy2, int xx2) { return sum[yy2][xx2] - sum[yy1][xx2] - sum[yy2][xx1] + sum[yy1][xx1]; }; if(num == 1) return calc(y1, x1, y2, x2); int res = 0; for(int mx = x1; mx <= x2; ++mx) { res = max(res, min(calc(y1, x1, y2, mx), solve(y1, mx, y2, x2, num - 1, sum))); res = max(res, min(calc(y1, mx, y2, x2), solve(y1, x1, y2, mx, num - 1, sum))); } for(int my = y1; my <= y2; ++my) { res = max(res, min(calc(y1, x1, my, x2), solve(my, x1, y2, x2, num - 1, sum))); res = max(res, min(calc(my, x1, y2, x2), solve(y1, x1, my, x2, num - 1, sum))); } if(num == 4) { for(int my1 = y1; my1 <= y2; ++my1) { for(int my2 = y1; my2 <= y2; ++my2) { vector<int> v1(x2 + 1), v2(x2 + 1); for(int mx = x1; mx <= x2; ++mx) { v1[mx] = min(calc(y1, x1, my1, mx), calc(y1, mx, my2, x2)); v2[mx] = min(calc(my1, x1, y2, mx), calc(my2, mx, y2, x2)); } if(my1 < my2) swap(v1, v2); for(int mx = x1 + 1; mx <= x2; ++mx) { v1[mx] = max(v1[mx], v1[mx - 1]); } for(int mx = x2 - 1; mx >= x1; --mx) { v2[mx] = max(v2[mx], v2[mx + 1]); } if(my1 == my2) { res = max(res, min(v1.back(), v2[0])); } else { for(int mx = x1; mx <= x2; ++mx) { res = max(res, min(v1[mx], v2[mx])); } } } } } return res; }; int main() { int h, w, n; cin >> h >> w >> n; vector<vector<int>> sum(h + 1, vector<int>(w + 1)); for(int i = 1; i <= h; ++i) { for(int j = 1; j <= w; ++j) { cin >> sum[i][j]; } } for(int i = 1; i <= h; ++i) { for(int j = 0; j < w; ++j) { sum[i][j + 1] += sum[i][j]; } } for(int i = 0; i < h; ++i) { for(int j = 1; j <= w; ++j) { sum[i + 1][j] += sum[i][j]; } } cout << solve(0, 0, h, w, n, sum) << endl; }
感想
全探索注意力ゲー。なんで600に置かれてるんだ？
function で再帰書いたら 2sec ぐらいになってしまったのでやめた。これは 1sec ぐらい。
試してないけど、めっちゃ頑張ったら O(M^4) 間に合ったりしないかな。
AOJ 2692 - ICPC Teams
解法
包除原理。
チームにしないといけない組は確定で組ませる。
また、チームにしてはいけない組のすべての部分集合に対して、その集合に含まれる組は確定でチームを組ませるとする。
このとき、チームの人数を3人ずつにできなくなるようなら無視する（4人以上のチームがある、2人確定したチーム数が多すぎるなど）。
すると、3人チームがいくつかと2人チームがいくつかになって、ほかは全部自由という条件になる。
自由な人から2人チームに割り当てて、あとは3人グループを作るだけ。
このときの場合の数は簡単な組み合わせ（高校数学の教科書に乗ってそうなぐらい典型なので書かないけど）で求まる。
これを最初に述べた部分集合のサイズに対して包除原理すれば求まる。
ソースコード
#include <bits/stdc++.h> using namespace std; // mint (mod とるライブラリ), union_find は省略 int main() { int n, m; cin >> n >> m; n *= 3; // to number of people map<int, int> idx; vector<int> a(m), b(m), c(m), ban; for(int i = 0; i < m; ++i) { cin >> a[i] >> b[i] >> c[i]; if(c[i] == 1) { ban.push_back(i); } } const int sz = [&] (){ // compress vector<int> xs; for(int i = 0; i < m; ++i) { xs.push_back(a[i]); xs.push_back(b[i]); } sort(begin(xs), end(xs)); xs.erase(unique(begin(xs), end(xs)), xs.end()); for(int i = 0; i < m; ++i) { a[i] = lower_bound(begin(xs), end(xs), a[i]) - begin(xs); b[i] = lower_bound(begin(xs), end(xs), b[i]) - begin(xs); } return xs.size(); }(); mint ans = 0; vector<mint> inv6_fact(n, mint(1)); { const mint inv6 = mint(6).inverse(); for(int i = 1; i < n; ++i) { inv6_fact[i] = inv6_fact[i - 1] * inv6; } } for(int S = 0; S < (1 << ban.size()); ++S) { // same team union_find uf(sz); for(int i = 0; i < m; ++i) { if(c[i] == 1) continue; uf.unite(a[i], b[i]); } for(int i = 0; i < (int)ban.size(); ++i) { if(S & (1 << i)) { uf.unite(a[ban[i]], b[ban[i]]); } } int cnt_two = 0, cnt_three = 0; { bool check = true; vector<bool> f(sz); for(int i = 0; i < sz; ++i) { if(f[uf.root(i)]) continue; f[uf.root(i)] = true; check &= uf.size(i) <= 3; cnt_three += uf.size(i) == 3; cnt_two += uf.size(i) == 2; } check &= (n - cnt_three * 3 - cnt_two * 2) >= cnt_two; if(!check) continue; // not count } int tn = n - cnt_three * 3 - cnt_two * 2; mint tans = comb(tn, cnt_two) * fact(cnt_two); tn -= cnt_two; tans *= fact(tn) * inv6_fact[tn / 3] * fact(tn / 3, true); if(__builtin_popcount(S) & 1) { ans -= tans; } else { ans += tans; } } cout << ans << endl; }
感想
AtCoder Beginner Contest で出ても違和感ないなって感じの数え上げ典型だった。
AOJ 1628 - Floating-Point Numbers
解説
実装するだけ。
仮数部表現は 1 も含めた 53 bit で表現すると楽だと思う。
a を何回足せば仮数部に収まらなくなるかは簡単な式で O(1) で求まる。
それを今の値に足し、exp を 1 増やして現在の仮数部と a を 1bit 右シフトするだけ。
これを n が 0 になるか a が 0 になるまで繰り返せば O(logn) で解ける。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ll n; while(cin >> n, n) { ll a = 1LL << 52; for(int i = 51; i >= 0; --i) { char b; cin >> b; a |= (ll)(b == '1') << i; } ll ex = 0, sig = a; while(n > 0 && a != 0) { const ll cnt = min(n, ((1LL << 53) - sig + a - 1) / a); sig += a * cnt; while(sig >= 1LL << 53) { ex += 1; sig >>= 1; a >>= 1; } n -= cnt; } cout << bitset<64>((ex << 52) | (sig & ((1LL << 52) - 1))) << endl; } }
感想
ICPC E 問題とは思えない軽実装。
もうちょっと重いのを置いてくれてもいいのよ。
AOJ 2604 - Pattern Language
解法
変数は 10 個しかないので、それぞれの変数を何桁にするか最初に全探索する。
すると、変数の桁ごとに、どの桁と対応するかを決定できる。
対応する集合を union find 木かなにかで管理しておく。
次に面倒なのは2桁目の値を何にするかに応じて1桁目の上限が変わることだが、これも 2^10 通り全探索して間に合う。
すると、union find の各集合が取れる値の範囲が簡単に求まるので、あとは全部掛け合わせるだけ。
O(2^(2m) m) で解ける。
追記：冷静に考えたら 1桁 or 2桁でmaxじゃない or 2桁でmax の3通りで O(3^m m) でいいじゃん。何やってんだか。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; constexpr int mod = 1e9 + 7; class union_find { public: union_find(int n) : par(n, -1) {} int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); } void unite(int x, int y) { x = root(x), y = root(y); if(x == y) return; if(par[x] < par[y]) swap(x, y); par[x] += par[y]; par[y] = x; } private: vector<int> par; }; int main() { int n, m; cin >> n >> m; string s; cin >> s; vector<char> var(m); vector<int> u(m); for(int i = 0; i < m; ++i) { cin >> var[i] >> u[i]; } ll ans = 0; for(int S1 = 0; S1 < (1 << m); ++S1) { // determine 1 digit or 2 digits { bool check = true; for(int i = 0; i < m; ++i) { check &= !(S1 & (1 << i)) || (u[i] >= 10); } if(!check) continue; } vector<pii> vs; for(int i = 0; i < n; ++i) { if(isdigit(s[i])) { vs.emplace_back(-1, s[i] - '0'); } else { const int id = find(begin(var), end(var), s[i]) - begin(var); if(S1 & (1 << id)) { vs.emplace_back(id, 2); } vs.emplace_back(id, 1); } } // integrate auto ss = vs; sort(begin(ss), end(ss)); ss.erase(unique(begin(ss), end(ss)), end(ss)); const int vsz = vs.size(); const int sz = ss.size(); union_find uf(sz); for(int i = 0; i < vsz; ++i) { const int id1 = lower_bound(begin(ss), end(ss), vs[i]) - begin(ss); const int id2 = lower_bound(begin(ss), end(ss), vs[vsz - i - 1]) - begin(ss); uf.unite(id1, id2); } // determine 2nd digit for(int S2 = 0; S2 < (1 << m); ++S2) { { bool check = (S1 & S2) == S2; for(int i = 0; i < m; ++i) { check &= !(S2 & (1 << i)) || u[i] >= 10; } if(!check) continue; } vector<ll> lb(sz, 0), ub(sz, mod); for(int i = 0; i < sz; ++i) { const int id = uf.root(i); const int midx = ss[i].first; ub[id] = min(ub[id], 9LL); if(midx == -1) { lb[id] = max(lb[id], (ll)ss[i].second); ub[id] = min(ub[id], (ll)ss[i].second); } else if(ss[i].second == 2) { lb[id] = max(lb[id], 1LL); if(S2 & (1 << midx)) { lb[id] = max(lb[id], (ll)(u[midx] / 10)); ub[id] = min(ub[id], (ll)(u[midx] / 10)); } else { ub[id] = min(ub[id], (ll)(u[midx] / 10 - 1)); } } else { if(S2 & (1 << midx) || u[midx] < 10) { ub[id] = min(ub[id], (ll)(u[midx] % 10)); } } } ll tans = 1; for(int i = 0; i < sz; ++i) { if(ub[i] == mod) continue; (tans *= max(0LL, ub[i] - lb[i] + 1)) %= mod; } (ans += tans) %= mod; } } cout << ans << endl; }
感想
i やら id やら midx やらわかりにくい実装になっちゃった。反省。
