AOJ 1322 - ASCII Expression
解法
今の左端と、上下の区間を持ちながら構文解析を書く。
base の位置は左から見ていって、初めて空白以外が現れた行としてよい。
分数表記のときに余計な space がたくさん入ることがあるので、base を見つける関数を切り分けてそこで左端の位置も更新しながらやればいいと思う。
ほかはいつもの構文解析と全く同じなので特に困ることはない。
最初問題を読んでなくて、有理数表現で計算してたら答えが合わなくて泣いてた。
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int mod = 2011; int add(int a, int b) { return (a + b) % mod; } int mul(int a, int b) { return a * b % mod; } int inv(int n) { int a = n, b = mod, u = 1, v = 0; while(b) { const int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } (u += mod) %= mod; return u; } int expr(int& x, int y1, int y2, vector<string> const&); int term(int& x, int y1, int y2, vector<string> const&); int factor(int& x, int y1, int y2, vector<string> const&); int powexpr(int& x, int y1, int y2, vector<string> const& s); int find_base(int& x, int y1, int y2, vector<string> const& s) { int res = -1; while(res == -1) { assert("[base] cannot find base" && x < (int)s[0].size()); for(int y = y1; y < y2; ++y) { if(s[y][x] == '.') continue; res = y; break; } x += (res == -1); } return res; } int digit(int& x, int y1, int y2, vector<string> const& s) { const int base_y = find_base(x, y1, y2, s); assert(isdigit(s[base_y][x])); return s[base_y][x++] - '0'; } int expr(int& x, int y1, int y2, vector<string> const& s) { // find base const int base_y = find_base(x, y1, y2, s); auto res = term(x, y1, y2, s); while(x + 1 < (int)s[0].size() && (s[base_y][x + 1] == '-' || s[base_y][x + 1] == '+')) { ++x; // space const char op = s[base_y][x]; x += 2; const auto r = term(x, y1, y2, s); if(op == '+') res = add(res, r); else if(op == '-') res = add(res, mod - r); else assert("[expr] invalid op" && false); } return res; } int term(int& x, int y1, int y2, vector<string> const& s) { const int base_y = find_base(x, y1, y2, s); auto res = factor(x, y1, y2, s); while(x + 1 < (int)s[0].size() && s[base_y][x + 1] == '*') { ++x; // space assert("[term] invalid op" && s[base_y][x] == '*'); x += 2; // op res = mul(res, factor(x, y1, y2, s)); } return res; } int factor(int& x, int y1, int y2, vector<string> const& s) { const int base_y = find_base(x, y1, y2, s); if(s[base_y][x] == '-' && s[base_y][x + 1] == '-') { // fraction int x1 = x + 1, x2 = x + 1; auto a = expr(x1, y1, base_y, s); auto b = expr(x2, base_y + 1, y2, s); x = max(x1, x2) + 1; return mul(a, inv(b)); } else if(s[base_y][x] == '-') { // neg x += 2; return mul(factor(x, y1, y2, s), 2010); } else { return powexpr(x, y1, y2, s); } } // primary is in int powexpr(int& x, int y1, int y2, vector<string> const& s) { const int base_y = find_base(x, y1, y2, s); int res = 1; if(s[base_y][x] == '(') { x += 2; res = expr(x, y1, y2, s); x += 2; // ".)" } else { assert(isdigit(s[base_y][x])); res = digit(x, base_y, base_y + 1, s); } if(base_y != 0 && isdigit(s[base_y - 1][x])) { // power int cnt = digit(x, base_y - 1, base_y, s); int t = 1; while(--cnt >= 0) { t = mul(t, res); } res = t; } return res; } int main() { int n; while(cin >> n, n) { vector<string> s(n); for(auto& ss : s) cin >> ss; int p = 0; cout << expr(p, 0, n, s) << endl; } }
感想
ついに倒せたー。
個人的には Matrix Calculator のほうが虚無だった．
AOJ 2017 - Karakuri Doll
解法
行きの位置、向き、戻りの位置、向きを同時にもって遷移するだけなんだけど、結構めんどくさい。
一番楽なのは DFS で1マスずつ動かしていくのだと思う。
曲がれるタイミングは、行きの位置の前にあるのが壁で、かつ、戻りの位置を回転させたときに目の前に壁がある時。
戻りの位置の曲がる場所の候補は複数あるけど、DFS するときに、戻りの位置と行きの位置を同時に移動するのではなくて、別々に移動させてやると実装がスッキリする。
accomplish になるのは、行き・戻りの両方の位置が M にあって、行きの位置の前に壁があり、戻りの位置の前に壁がないとき。
実装上の注意
- DFS にすると手元だとオプションつけないとスタックオーバーフローするかも
- 到達したかのフラグを vector で持つと MLE するので、グローバルの bool 配列にしよう
ソースコード
#include <bits/stdc++.h> using namespace std; // direction // 0: N, 1: E, 2:S, 3:W constexpr int dx[4] = {0, 1, 0, -1}; constexpr int dy[4] = {-1, 0, 1, 0}; constexpr int dd[2] = {1, 3}; // turn right, left bool reach1[16][64][4]; // only go to kitchen bool reach[16][64][4][16][64][4]; int main() { int w, h; while(cin >> w >> h, w) { memset(reach1, false, sizeof(reach1)); memset(reach, false, sizeof(reach)); vector<string> v(h); for(auto& s : v) cin >> s; int sy = -1, sx = -1, sd = -1, gy = -1, gx = -1; for(int i = 0; i < h; ++i) { for(int j = 0; j < w; ++j) { if(v[i][j] == '#') continue; if(v[i][j] == 'K') { sy = i, sx = j; for(int d = 0; d < 4; ++d) { if(v[sy + dy[d]][sx + dx[d]] == '#') continue; sd = d; } } if(v[i][j] == 'M') { gy = i, gx = j; } } } function<bool(int, int, int)> go_to_kitchen = [&] (int y, int x, int d) { if(reach1[y][x][d]) return false; reach1[y][x][d] = true; if(y == gy && x == gx) return true; bool res = false; if(v[y + dy[d]][x + dx[d]] != '#') { res = go_to_kitchen(y + dy[d], x + dx[d], d); } else { res = go_to_kitchen(y, x, (d + 1) % 4); res |= go_to_kitchen(y, x, (d + 3) % 4); } return res; }; function<bool(int, int, int, int, int, int)> dfs = [&] (int y1, int x1, int d1, int y2, int x2, int d2) { if(reach[y1][x1][d1][y2][x2][d2]) return false; reach[y1][x1][d1][y2][x2][d2] = true; if(gy == y2 && gx == x2 && gy == y1 && gx == x1 && v[y2 - dy[d2]][x2 - dx[d2]] != '#' && v[y1 + dy[d1]][x1 + dx[d1]] == '#') { return true; } bool res = false; if(v[y1 + dy[d1]][x1 + dx[d1]] != '#') { res = dfs(y1 + dy[d1], x1 + dx[d1], d1, y2, x2, d2); } else { // can turn for(int i = 0; i < 2; ++i) { const int nd1 = (d1 + dd[i]) % 4, nd2 = (d2 + dd[i]) % 4; if(v[y2 - dy[nd2]][x2 - dx[nd2]] != '#') continue; // front must be wall res |= dfs(y1, x1, nd1, y2, x2, nd2); } } if(v[y2 + dy[d2]][x2 + dx[d2]] != '#') { res |= dfs(y1, x1, d1, y2 + dy[d2], x2 + dx[d2], d2); } return res; }; bool ac = false; for(int d = 0; d < 4; ++d) { ac |= dfs(sy, sx, sd, sy, sx, d); } if(ac) { cout << "He can accomplish his mission." << endl; } else if(go_to_kitchen(sy, sx, sd)) { cout << "He cannot return to the kitchen." << endl; } else { cout << "He cannot bring tea to his master." << endl; } } }
感想
最初の実装は行きと帰りの位置を同時に更新（前計算で曲がれる位置を求めておく感じ）してたので、実装が結構重くなってた。
片方ずつ動かすときれいにかけるんだなあ。
かなりバグったが、サンプルが強くて助かった。
AOJ 2623 - Optimal alpha beta pruning
解法
普通にαβ法をメモ化再帰でやるだけ。minimize も maximize も同じ。
dp[v][alpha][beta] := negamax(v, alpha, beta) で最善の選び方をした時の解
子供の順番は next_permutation で全部試してOK。
葉の探索回数をあえて少なくして、その代わりとして返り値を小さくするように潜ったほうがいいこともあるのでは？とか一瞬考えちゃったけど、今の状態から最初に潜る子の結果をどうするかは選択できないので、全探索だけで良かった。
計算量は O(5! n^3) だけど、どう考えてもこんなに遅くならないので、余裕で間に合う。
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int inf = 1e9; template<typename T> std::vector<T> table(int n, T v) { return std::vector<T>(n, v); } template <class... Args> auto table(int n, Args... args) { auto val = table(args...); return std::vector<decltype(val)>(n, std::move(val)); } int main() { int n; cin >> n; vector<int> p(n), vs = {-inf, inf}; for(auto& x : p) { cin >> x; vs.push_back(x); vs.push_back(-x); } sort(begin(vs), end(vs)); vs.erase(unique(begin(vs), end(vs)), end(vs)); auto get_idx = [&] (int val) -> int { return lower_bound(begin(vs), end(vs), val) - begin(vs); }; vector<vector<int>> g(n); for(int i = 0; i < n; ++i) { int k; cin >> k; g[i].resize(k); for(auto& c : g[i]) { cin >> c; c--; } } auto max_dp = table(n, vs.size(), vs.size(), make_pair(-inf, 0)); auto min_dp = table(n, vs.size(), vs.size(), make_pair(inf, 0)); function<pii(int, int, int, bool)> dfs = [&] (int v, int alpha, int beta, bool is_min) { if(g[v].empty()) return make_pair(1, p[v]); // leaf auto& res = (is_min ? min_dp[v][alpha][beta] : max_dp[v][alpha][beta]); if(abs(res.first) != inf) return res; sort(begin(g[v]), end(g[v])); do { int talpha = alpha; pii cur = make_pair(0, -inf); for(auto const ch : g[v]) { auto val = dfs(ch, get_idx(-vs[beta]), get_idx(-vs[talpha]), is_min); val.second = -val.second; cur.first += val.first; if(val.second >= vs[beta]) { cur.second = val.second; break; } if(val.second > vs[talpha]) { talpha = get_idx(val.second); } } if(cur.second == -inf) { // not occured val.second >= beta cur.second = vs[talpha]; } if(is_min) res = min(res, cur); else res = max(res, cur); } while(next_permutation(begin(g[v]), end(g[v]))); return res; }; cout << dfs(0, 0, vs.size() - 1, true).first << " " << dfs(0, 0, vs.size() - 1, false).first << endl; }
感想
問題文を読むのに少し手間取った。
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) 間に合ったりしないかな。
