AOJ 2385 - Shelter
解法
こんなの積分するしかないでしょという気分になるので立式する。
とりあえずボロノイ図を考えると、凸多角形領域 \(D\) とその内部の1点に対する問題に帰着できる。
内部の点を \((a, b)\) とする。
この上で式を立てると $$\int\!\!\!\int_D (x - a)^2 + (y - b)^2 dxdy$$ となる。
グリーンの定理より $$\oint_{\partial D} -\frac{1}{3}(y - b)^3dx + \frac{1}{3}(x - a)^3dy$$ を求めればよい。
多角形上の線分の端点を \((x_1, y_1), (x_2, y_2)\) とすれば、\(0 \leq t \leq 1\) を用いて $$x = x_1 + (x_2 - x_1)t$$ $$y = y_1 + (y_2 - y_1)t$$ とおけて、求める周回積分は $$-\frac{1}{3}\int_0^1 \{(y_2 - y_1)t + (y_1 - b)\}^3(x_2 - x_1)dt \\ + \frac{1}{3}\int_0^1 \{(x_2 - x_1)t + (x_1 - a)\}^3(y_2 - y_1)dt$$ となる（厳密にはすべての線分に対してこれを求めて総和を取る）。
これを頑張って手計算して答えを得る。最後に全体の面積で割るのを忘れないように。
ボロノイ図を作るのに \(O(n^3)\) かかるが、\(n \leq 100\) なので間に合う。
ソースコード
#include <bits/stdc++.h> using namespace std; using ld = long double; using point = std::complex<ld>; using polygon = std::vector<point>; constexpr ld eps = 1e-10; 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; // a -> b -> c : counterclockwise if(cross(b, c) < -eps) return -1; // a -> b -> c : clockwise if(dot(b, c) < 0) return 2; // c -> a -> b : line if(std::norm(b) < std::norm(c)) return -2; // a -> b -> c : line return 0; // a -> c -> b : line } struct line { line() : a(0, 0), b(0, 0) {} line(point a, point b) : a(a), b(b) {} point a, b; }; point is_ll(line s, line t) { point sv = s.b - s.a, tv = t.b - t.a; assert(cross(sv, tv) != 0); return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv); } // left side polygon convex_cut(polygon const& p, line l) { const int N = p.size(); polygon res; for(int i = 0; i < N; ++i) { auto a = p[i], b = p[(i + 1) % N]; if(ccw(l.a, l.b, a) != -1) { res.push_back(a); } if(ccw(l.a, l.b, a) * ccw(l.a, l.b, b) < 0) { if(cross(a - b, l.a - l.b) == 0) continue; // cut line が辺に覆いかぶさる res.push_back(is_ll(line(a, b), l)); } } return res; } ld area(polygon const& p) { const int N = p.size(); ld res = 0; for(int i = 0; i < N; ++i) { res += cross(p[i], p[(i + 1) % N]); } return res / 2; } line separate_line(point const& p1, point const& p2) { const auto mid = (p1 + p2) * 0.5L; return line{mid, mid + (mid - p1) * point(0, 1)}; } int main() { int m, n; cin >> m >> n; polygon ps(m), shelter(n); for(int i = 0; i < m; ++i) { int x, y; cin >> x >> y; ps[i] = point(x, y); } for(int i = 0; i < n; ++i) { int x, y; cin >> x >> y; shelter[i] = point(x, y); } ld ans = 0; for(int i = 0; i < n; ++i) { auto range = ps; for(int j = 0; j < n; ++j) { if(i == j) continue; auto l = separate_line(shelter[i], shelter[j]); if(cross(shelter[i] - l.a, l.b - l.a) > 0) { swap(l.a, l.b); } range = convex_cut(range, move(l)); } const int sz = range.size(); const auto a = real(shelter[i]), b = imag(shelter[i]); for(int j = 0; j < sz; ++j) { const ld x1 = real(range[j]), y1 = imag(range[j]); const ld x2 = real(range[(j + 1) % sz]), y2 = imag(range[(j + 1) % sz]); const ld t1 = (x2 - x1) * (pow(y2 - y1, 3) / 4 + pow(y2 - y1, 2) * (y1 - b) + 1.5 * (y2 - y1) * pow(y1 - b, 2) + pow(y1 - b, 3)); const ld t2 = (y2 - y1) * (pow(x2 - x1, 3) / 4 + pow(x2 - x1, 2) * (x1 - a) + 1.5 * (x2 - x1) * pow(x1 - a, 2) + pow(x1 - a, 3)); ans += t2 - t1; } } ans /= 3 * area(ps); cout << fixed << setprecision(10) << ans << endl; }
感想
グリーンの定理とか久々に使った（使わなくても直感的に式は出せる気もする、どうなんだろう）。
AOJ 2569 - Putter
解法
線分の通り方を n! 通り全探索する。
ある線分を通る時に、その線分で点を鏡写しにしていけば、直線がそれらの線分を貫くかどうか、という問題になる。
この判定は角度（厳密にはベクトル）で行う。
始点から、ある線分を通るような範囲をベクトルで表すことにする。
つまり、始点から線分の端点へのベクトル2つを、より反時計回り方向にある方とそうでない方で管理する。
すべての範囲が共通部分を持てばOK。
そのために、反時計回りにある方のベクトルだけを考えて、それらの中でもっとも時計回り方向にあるものを考える（時計回りの方は逆）。
こうして得られた2つのベクトルが、反時計回りのほうがちゃんと反時計回りの方にあるならOK。
ここまでの計算は全部外積だけでできる。
ただし、反時計回りのやつを時計回りに、時計回りのやつを反時計回りの方に寄せていった結果、最終的に寄せた大きさが180度を超えて条件合致してしまうケースがある。
なので、最も（反）時計まわりにあるものを考えるというよりは、ベクトルの範囲を1つずつ見ていって、常に共通部分を持つもの、とする。
convex polygon なのでこれでちゃんと判定可能（今条件合致していて、次に鏡写しにしたときのベクトルの範囲を考えたときに、範囲が大きく変動して、偶然条件合致と判定されないということ）。
ソースコード
#include <bits/stdc++.h> using namespace std; using ld = double; using point = std::complex<ld>; using polygon = std::vector<point>; struct line { line() : a(0, 0), b(0, 0) {} line(point a_, point b_) : a(a_), b(b_) {} point a, 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); } point proj(line const& l, point const& p) { ld t = dot(p - l.a, l.a - l.b) / std::norm(l.a - l.b); return l.a + t * (l.a - l.b); } point reflect(line const& l, point const& p) { return p + (proj(l, p) - p) * 2.0; } point read_point() { ld x, y; cin >> x >> y; return point{x, y}; } int main() { int n; while(cin >> n, n) { const auto sp = read_point(); polygon ps; for(int i = 0; i < n; ++i) { ps.emplace_back(read_point()); } vector<int> ord(n); iota(begin(ord), end(ord), 0); int ans = 0; do { auto ts = ps; vector<point> lvs, rvs; for(auto i : ord) { const auto a = ts[i], b = ts[(i + 1) % n]; lvs.push_back(a + (b - a) / abs(b - a) * 1e-6 - sp); rvs.push_back(b + (a - b) / abs(b - a) * 1e-6 - sp); if(cross(rvs.back(), lvs.back()) < 0) swap(lvs.back(), rvs.back()); for(int j = 0; j < n; ++j) { if(j == i || (i + 1) % n == j) continue; ts[j] = reflect(line{a, b}, ts[j]); } } auto lv = lvs[0], rv = rvs[0]; bool check = true; for(int i = 1; i < n; ++i) { if(cross(lv, lvs[i]) <= 0) swap(lv, lvs[i]); if(cross(rv, rvs[i]) >= 0) swap(rv, rvs[i]); check &= cross(rv, lv) >= 0; } ans += check; } while(next_permutation(begin(ord), end(ord))); cout << ans << endl; } }
感想
（反）時計回り側のベクトルを全部統合してから判定してて最初死んでいた。
多分本番だと無限に悩むやつ。そして多分通らないまま終わる。悲しいね。
AOJ 2164 - Revenge of the Round Table
解法
回転して同じものはとりあえず重複して数える。
というのも、もし周期 s の並べ方があったとしたら、回転して同じとみなせるものは s 通りだとわかるからだ。
まず、先頭を A に固定して、ループを考慮しない数え上げをする。
次に、ループを考慮して数え上げるが、これは先頭と末尾の A の個数を決め打ちして、間に B から始まって B で終わるものを考えればOK.
これで先頭 A でループも考慮したものが得られて、先頭を B にしたものも同じなので 2 倍する。
さっきので求まったテーブルを dp[i] とすると、周期が i で長さも i であるような列の総数 dp2[i] は
dp2[i] = dp[i] - (i のすべての約数 j に対して dp2[j] の総和)
となる。
求める答えは、n のすべての約数について dp2[i] / i の総和となる。
計算量は O(N^2)
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int mod = 1000003; ll inv(ll n) { ll a = n, b = mod, u = 1, v = 0; while(b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= mod; if(u < 0) u += mod; return u; } int main() { int n, k; while(cin >> n >> k, n) { if(n == 1) { cout << 2 << endl; continue; } ll ans = 0; if(k >= n) { ans += 2; k = n - 1; } vector<vector<vector<int>>> dp1(n + 1, vector<vector<int>>(k + 1, vector<int>(2))); dp1[1][1][0] = 1; // start with A for(int i = 1; i < n; ++i) { for(int j = 1; j <= k; ++j) { for(int pre = 0; pre < 2; ++pre) { if(j + 1 <= k) { (dp1[i + 1][j + 1][pre] += dp1[i][j][pre]) %= mod; } (dp1[i + 1][1][!pre] += dp1[i][j][pre]) %= mod; } } } vector<ll> dp2(n + 1), sum(n + 1); for(int i = 1; i <= n; ++i) { for(int j = 0; j <= k; ++j) { (dp2[i] += dp1[i][j][1]) %= mod; // ends with B (sum[i] += dp1[i][j][0]) %= mod; } for(int loop = 2; loop <= min(k, i); ++loop) { (dp2[i] += 1LL * sum[i - loop] * (loop - 1)) %= mod; } (dp2[i] += dp2[i]) %= mod; // consider starting with B } vector<int> dp3(n + 1); for(int i = 1; i <= n; ++i) { dp3[i] = dp2[i]; for(int j = 1; j < i; ++j) { if(i % j == 0) { (dp3[i] += mod - dp3[j]) %= mod; } } } for(int i = 1; i <= n; ++i) { if(n % i != 0) continue; (ans += dp3[i] * inv(i)) %= mod; } cout << ans << endl; } }
感想
n == 1 がコーナーケースになってる実装だから良くないなあ。
実装が悪い。
AOJ 2343 - Matrix Operation
解法
操作に必要な情報は、
- 鏡写しの状態になっているか
- 何回転しているか
- どこに何が書き込まれたか (WR, CP)
- 列 or 行の並びはどうなっているか
だけなので、各操作に対し O(1) or O(logQ) で可能。
操作で与えられた位置にたいし、それが初期状態でどこのマスだったかを計算するような関数を作っておけば、あとはその上でやるだけになる。
この変換関数の実装はいろいろやり方があると思う。
自分は「鏡写しか」「何回転したか」から、列と行がもともとの列 or 行のどっちに対応するか、0 -> n の方向なのか n -> 0 の方向なのか、を先に考えて配列で持っておいた。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; constexpr int mod = 1e9 + 7; constexpr int rev_tbl[2][4][2] = { // [mir][rot][row/col] {{0, 0}, {1, 0}, {1, 1}, {0, 1}}, {{0, 1}, {1, 1}, {1, 0}, {0, 0}} }; int main() { ll n, q, A, B, C, D, E, F, G; cin >> n >> q >> A >> B >> C >> D >> E >> F >> G; vector<string> op(q); vector<int> w(q), x(q), y(q), z(q); for(int i = 0; i < q; ++i) { cin >> op[i]; if(op[i] == "WR") cin >> w[i] >> x[i] >> y[i]; else if(op[i] == "CP") cin >> w[i] >> x[i] >> y[i] >> z[i]; else if(op[i] == "SR") cin >> w[i] >> x[i]; else if(op[i] == "SC") cin >> w[i] >> x[i]; } int mir = 0, rot = 0; vector<int> ridx(n), cidx(n); iota(begin(ridx), end(ridx), 1); iota(begin(cidx), end(cidx), 1); auto get_r_idx = [&] (int r) -> int& { const int i = (rev_tbl[mir][rot][0] ? n - r : r - 1); return rot & 1 ? cidx[i] : ridx[i]; }; auto get_c_idx = [&] (int c) -> int& { const int i = (rev_tbl[mir][rot][1] ? n - c : c - 1); return rot & 1 ? ridx[i] : cidx[i]; }; auto get_orig_pos = [&] (int r, int c) { if(rot & 1) return make_pair(get_c_idx(c), get_r_idx(r)); else return make_pair(get_r_idx(r), get_c_idx(c)); }; map<pii, int> v; for(int i = 0; i < q; ++i) { if(op[i] == "WR") { int r, c; tie(r, c) = get_orig_pos(w[i], x[i]); v[{r, c}] = y[i]; } else if(op[i] == "CP") { int r1, c1, r2, c2; tie(r1, c1) = get_orig_pos(w[i], x[i]); tie(r2, c2) = get_orig_pos(y[i], z[i]); if(v.count({r1, c1})) { v[{r2, c2}] = v[{r1, c1}]; } else { v[{r2, c2}] = (r1 * A + c1 * B) % C; } } else if(op[i] == "SR") { swap(get_r_idx(w[i]), get_r_idx(x[i])); } else if(op[i] == "SC") { swap(get_c_idx(w[i]), get_c_idx(x[i])); } else if(op[i] == "RL") { if(mir) rot = (rot + 3) % 4; else rot = (rot + 1) % 4; } else if(op[i] == "RR") { if(mir) rot = (rot + 1) % 4; else rot = (rot + 3) % 4; } else if(op[i] == "RH") { mir = !mir; rot = (rot + 2) % 4; } else if(op[i] == "RV") { mir = !mir; } } ll h = 314159265; for(int r = D; r <= E; ++r) { for(int c = F; c <= G; ++c) { int rr, cc; tie(rr, cc) = get_orig_pos(r, c); const ll val = v.count({rr, cc}) ? v[{rr, cc}] : (rr * A + cc * B) % C; h = (h * 31 + val) % mod; } } cout << h << endl; }
感想
こういうのめっちゃ頭壊れるんだよなー。
本番で出たら泣きそうになるタイプのやつ（注意力ゲームなので）。
AOJ 2430 - Longest Increasing Sequence
解法
やり方は2通りあるんですが、片方はちょっとメモリが厳しかった（通ったけど）。
メモリが厳しいほう
dp[i][j] := i 個目までみて最大長さが j であるときの右端の min
と定義。各 i に対して、最初に dp[i] の j が大きい方から累積 min を取る。
遷移は、j = i + 1, ... に対して、区間 [i, j] の和 S を持ちながら dp[i] において S 以上となる最大位置 L を二分探索で求めて dp[j][L] を更新する。
復元テーブルは適当に (idx, len) を持てば可能。
計算量は O(N^2logN) だが、dp テーブルの要素が long long であること、N <= 4000 であること、復元テーブルも必要なのも合わせて、適当に書くと MLE する。
DP テーブルで明らかに不要なサイズなどを持っておかないようにすると、ギリギリ (150MB ぐらい？）で通った。
ましにする
dp[i][j] := i 個目までみて右端の値が j であるときの最大長さ
と定義。j が sum なので map で管理する。
ぶっちゃけさっきのを key と value を入れ替えて map にしただけ。
map のデータは、任意の (ki, vi), (kj, vj) in map に対して ki < kj => vi < vj を満たすように持っておく。
すると、さっきの遷移で、今の和 S に対してどれを使えばいいか二分探索できる。
これも O(N^2logN) で動作し、かなり省メモリになる。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; constexpr ll inf = 1e18; int main() { int n; cin >> n; vector<ll> a(n); for(auto& aa : a) cin >> aa; vector<map<ll, int>> dp(n + 1); vector<map<ll, pair<ll, int>>> pre(n + 1); dp[0][-inf] = 0; for(int i = 0; i < n; ++i) { ll sum = 0; for(int j = i + 1; j <= n; ++j) { sum += a[j - 1]; auto it = dp[i].lower_bound(sum); if(it == dp[i].begin()) continue; it = prev(it); { // update auto nit = dp[j].lower_bound(sum); while(nit != end(dp[j]) && nit->second <= it->second + 1) { pre[j].erase(nit->first); nit = dp[j].erase(nit); } if(nit == begin(dp[j]) || prev(nit)->second < it->second + 1) { dp[j][sum] = it->second + 1; pre[j][sum] = {it->first, i}; } } } } int max_len = 0; ll cur_sum = 0, cur_idx = n; for(auto const& p : dp[n]) { if(max_len < p.second) { max_len = p.second; cur_sum = p.first; } } vector<int> ans; while(pre[cur_idx].count(cur_sum)) { const auto p = pre[cur_idx][cur_sum]; ans.push_back(p.second); cur_sum = p.first, cur_idx = p.second; } ans.pop_back(); reverse(begin(ans), end(ans)); cout << ans.size() + 1 << endl; for(int i = 0; i < (int)ans.size(); ++i) { cout << ans[i] << " \n"[i + 1 == (int)ans.size()]; } }
感想
復元パートもっとうまくできる気がするんだけど、楽なのはこれだと思うんだよなあ。
というかなんでこんなに MLE きついんだろう。もっと賢く解けってこと？
AOJ 1341 - Longest Chain
解法
動的2次元セグ木とかで解けそうだけど、ICPC でデータ構造の問題はチームメイトに投げるため違う解き方をする。
とりあえずソートができるので3次元 -> 2次元になる。
1次元のときの LIS と違うのは、長さ L の末尾として最適なものが定まらない（全順序じゃないから）ということ。
なので、末尾の最小値の代わりに、最適になりうる集合を持つことにする。
この集合は、例えば {(y1, z1), (y2, z2), ...} としたら y1 < y2 < ... かつ z1 > z2 > ... となるように保持する。
y1 < y2 かつ z1 < z2 なる (y2, z2) は最適にならないからこれでOK。
あとは普通の LIS の要領で二分探索する（できる）。
(y, z) を長さ L の列の末尾にできる条件は、dp[L - 1] の要素で yi < y を満たす最大の yi に対して (yi, zi) < (y, z) であることが集合の持ち方から言える。
(y, z) を挿入するときは集合の条件を壊さないようにすること。
計算量は O(n(logn)^2)。
同じ y の値がくると面倒なので、最初に (y, z) の降順に並べておくと楽。
ソースコード
#include <bits/stdc++.h> using namespace std; int a, b; constexpr int C = ~(1 << 31); constexpr int M = (1 << 16) - 1; int r() { a = 36969 * (a & M) + (a >> 16); b = 18000 * (b & M) + (b >> 16); return (C & ((a << 16) + b)) % 1000000; } struct point { int y, z; point(int y_, int z_) : y(y_), z(z_) {} bool operator<(point const& p) const { return y < p.y; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int m, n; while(cin >> m >> n >> a >> b, n + m) { vector<tuple<int, int, int>> ps(n + m); for(int i = 0; i < m; ++i) { int x, y, z; cin >> x >> y >> z; ps[i] = make_tuple(x, -y, -z); } for(int i = m; i < n + m; ++i) { const int x = r(), y = r(), z = r(); ps[i] = make_tuple(x, -y, -z); } sort(begin(ps), end(ps)); vector<point> ps2; for(int i = 0; i < n + m; ++i) { ps2.emplace_back(-get<1>(ps[i]), -get<2>(ps[i])); } int ans = 0; vector<set<point>> dp(n + m + 1); dp[0].emplace(0, 0); for(auto const& p : ps2) { auto check = [&] (int i) { auto it = dp[i].lower_bound(p); if(it == dp[i].begin()) return false; it = prev(it); return p.y > it->y && p.z > it->z; }; int lb = 0, ub = n + m; while(ub - lb > 1) { const int mid = (ub + lb) >> 1; (check(mid) ? lb : ub) = mid; } auto it = dp[ub].lower_bound(p); while(it != dp[ub].end() && it->z >= p.z) { it = dp[ub].erase(it); } if(it == dp[ub].begin() || prev(it)->z > p.z) { dp[ub].insert(p); } ans = max(ans, ub); } cout << ans << endl; } }
AOJ 2172 - Queen's Case
解法
ゲームの状態グラフにループがあるので、ただ DFS やるだけだとうまくいかない。
これは後退解析という手法で解けて、ど典型なので知らなかったら覚えてしまってよい（どの問題でも同じやり方だし）。
後退解析は、勝ち負けが確定できるところから探索していく手法で、最終的に勝ち負けが確定できない状態が、引き分けになる。
ググればいい記事がたくさんあるだろうからここには書かない。
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int dx[5] = {0, 0, 1, 0, -1}; constexpr int dy[5] = {0, 1, 0, -1, 0}; 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)); } enum { Escape, Caught, Undecided }; int main() { int w, h; while(cin >> w >> h, w) { vector<string> v(h); for(auto& a : v) cin >> a; auto can_move_to = [&] (int y, int x) { return 0 <= y && y < h && 0 <= x && x < w && v[y][x] != '#'; }; int qy = -1, qx = -1, ay = -1, ax = -1; auto dp = table(h, w, h, w, 2, Undecided); auto deg = table(h, w, h, w, 2, 0); queue<tuple<int, int, int, int, int>> que; for(int i = 0; i < h; ++i) { for(int j = 0; j < w; ++j) { if(v[i][j] == '#') continue; if(v[i][j] == 'Q') qy = i, qx = j; if(v[i][j] == 'A') ay = i, ax = j; for(int k = 0; k < h; ++k) { for(int l = 0; l < w; ++l) { if(v[k][l] == '#' || (k == i && l == j)) continue; for(int d = 0; d < 5; ++d) { const int ny1 = i + dy[d], nx1 = j + dx[d]; const int ny2 = k + dy[d], nx2 = l + dx[d]; deg[i][j][k][l][0] += can_move_to(ny1, nx1) && v[i][j] != 'E'; deg[i][j][k][l][1] += can_move_to(ny2, nx2); } if(v[i][j] == 'E') { dp[i][j][k][l][0] = Escape; deg[i][j][k][l][0] = 0; que.emplace(i, j, k, l, 0); } } } dp[i][j][i][j][0] = dp[i][j][i][j][1] = Caught; que.emplace(i, j, i, j, 0); que.emplace(i, j, i, j, 1); } } while(!que.empty()) { int qy, qx, ay, ax, turn; tie(qy, qx, ay, ax, turn) = que.front(); que.pop(); if(turn == 0) { // Queen's turn, so consider army's move for(int d = 0; d < 5; ++d) { const int nay = ay + dy[d], nax = ax + dx[d]; if(!can_move_to(nay, nax) || dp[qy][qx][nay][nax][!turn] != Undecided) continue; if(dp[qy][qx][ay][ax][turn] == Escape) { if(--deg[qy][qx][nay][nax][!turn] == 0) { dp[qy][qx][nay][nax][!turn] = Escape; que.emplace(qy, qx, nay, nax, !turn); } } else { deg[qy][qx][nay][nax][!turn] = 0; dp[qy][qx][nay][nax][!turn] = Caught; que.emplace(qy, qx, nay, nax, !turn); } } } else { for(int d = 0; d < 5; ++d) { const int nqy = qy + dy[d], nqx = qx + dx[d]; if(!can_move_to(nqy, nqx) || dp[nqy][nqx][ay][ax][!turn] != Undecided) continue; if(dp[qy][qx][ay][ax][turn] == Escape) { deg[nqy][nqx][ay][ax][!turn] = 0; dp[nqy][nqx][ay][ax][!turn] = Escape; que.emplace(nqy, nqx, ay, ax, !turn); } else { if(--deg[nqy][nqx][ay][ax][!turn] == 0) { dp[nqy][nqx][ay][ax][!turn] = Caught; que.emplace(nqy, nqx, ay, ax, !turn); } } } } } const auto ans = dp[qy][qx][ay][ax][0]; if(ans == Escape) { cout << "Queen can escape." << endl; } else if(ans == Caught) { cout << "Army can catch Queen." << endl; } else { cout << "Queen can not escape and Army can not catch Queen." << endl; } } }
感想
Caught になってるときに間違えて引き分けの出力しててサンプルが合わず無限に悩んでた（目がついてないね
