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 になってるときに間違えて引き分けの出力しててサンプルが合わず無限に悩んでた（目がついてないね
AOJ 2587 - Elevator Hall Number
解法
桁DPしようと思ったが、遷移がうまく書けないので困った。
そこでオートマトンをイメージする。
結論を言うと、a[i] の値で NFA を作ってから DFA に変換し、その上で DP する。
オートマトンとして考えるべき状態は、以下の4つがある。
- P[i] := i 番目のエレベーターまで完了直後
- Q[i] := i+1 番目のエレベーターの途中で、low の2桁目の値
- R[i] := i+1 番目のエレベーターの途中で、low と high の2桁目の間の値
- S[i] := i+1 番目のエレベーターの途中で、high の2桁目の値
low, high の値に応じて、P[i] -> Q[i], Q[i] -> P[i + 1], ... などの遷移を書く。
すると、NFA のノードの数は 4 * n + 1 個になる。
したがって、NFA のノードには P[i] = 4 * i, Q[i] = 4 * i + 1, ... と番号を振っておくと、DFA を作るときに bit で管理できる。
DFA の構築は普通に初期状態 P[0] から BFS して、各ノードに対し、遷移先の ID の集合をbitで管理すればOK。
DFA ができたらあとは普通の DP で、メモ化再帰でやるとすれば 終了状態 P[n] の時 1 であり、それ以外のときは遷移先をすべて足し合わせた値になる。
ただし、現状態が終了状態を含む場合（普通にありえます）は、この値に +1 する必要がある。
計算量は O(4^N * 10) 程度でおもそうだが、DFA の探索空間はたいしたことないから問題なし。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int n; while(cin >> n, n) { vector<int> low(n), high(n); for(int i = 0; i < n; ++i) { cin >> low[i] >> high[i]; } // build NFA const int fin = n * 4; // finish node vector<vector<vector<int>>> nfa(n * 4 + 1, vector<vector<int>>(10)); for(int i = 0; i < n; ++i) { if(low[i] < 10) { // Pi -> Pi+1 for(int x = low[i]; x <= min(9, high[i]); ++x) { nfa[i * 4][x].push_back(i * 4 + 4); } } else { // Pi -> Qi -> Pi+1 nfa[i * 4][low[i] / 10].push_back(i * 4 + 1); const int ub = low[i] / 10 == high[i] / 10 ? high[i] % 10 : 9; for(int x = low[i] % 10; x <= ub; ++x) { nfa[i * 4 + 1][x].push_back(i * 4 + 4); } } // Pi -> Ri -> Pi+1 for(int x = low[i] / 10 + 1; x < high[i] / 10; ++ x) { nfa[i * 4][x].push_back(i * 4 + 2); } for(int x = 0; x <= 9; ++x) { nfa[i * 4 + 2][x].push_back(i * 4 + 4); } if(high[i] >= 10) {// Pi -> Si -> Pi+1 nfa[i * 4][high[i] / 10].push_back(i * 4 + 3); const int lb = low[i] / 10 == high[i] / 10 ? low[i] % 10 : 0; for(int x = lb; x <= high[i] % 10; ++x) { nfa[i * 4 + 3][x].push_back(i * 4 + 4); } } } // build DFA map<int, array<int, 10>> dfa; { queue<int> que; que.push(1); set<int> vis = {1}; while(!que.empty()) { const int S = que.front(); que.pop(); for(int x = 0; x <= 9; ++x) { int nS = 0; for(int i = 0; i < 4 * n; ++i) { if(!(S & (1 << i))) continue; for(auto const to : nfa[i][x]) { nS |= 1 << to; } } dfa[S][x] = nS == 0 ? -1 : nS; if(nS == 0 || vis.count(nS)) continue; que.push(nS); vis.insert(nS); } } } map<int, ll> memo; function<ll(int)> solve = [&] (int S) { if(memo.count(S)) return memo[S]; if(S == (1 << fin)) return 1LL; for(int x = 0; x <= 9; ++x) { if(dfa[S][x] == -1) continue; memo[S] += solve(dfa[S][x]); } if(S & (1 << fin)) { memo[S] += 1; } return memo[S]; }; cout << solve(1) << endl; } }
感想
これむずい。
TDPC の文字列作るやつに似てるから1文字ずつ付け加えていって、無理やり一意的な表現にしようとしたけど無理だった。
AOJ 1317 - Weaker than Planned
解法
普通のバックトラックで解ける。
バックトラックするときは、どういう順番で探索すると枝刈りが起こりやすいかを考える必要がある。
今回なら、文字の種類数が多い方を先に考えたほうがよい（条件が厳しいので）。
あとは実装するだけだが、考えられる実装として
- 単語バッグを見ていって、使うか使わないかで場合分け。使うなら、文章中の単語を1つ選んで対応付ける
- 文章中の単語を見ていって、対応する単語を1つ選ぶ
の2通りあるが、後者のほうが早い。
単語バックを見ていく実装だと、使わない単語がたくさんあったときに無駄な探索がかなり発生する気がするので、まあそうかなという感じ（？）
ちなみに前者の実装でも通る。前者はちょうど 1sec ぐらいかかるが、まあ本番でもぎりぎり通るのではという気がする。
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n; while(cin >> n, n) { vector<string> ws(n); for(auto& w : ws) cin >> w; vector<string> ss = {""}; while(cin >> ss.back()) { if(ss.back().back() == '.') break; ss.push_back(""); } ss.back().pop_back(); // period const auto ts = ss; sort(begin(ss), end(ss), [] (string s1, string s2) { return set<char>{begin(s1), end(s1)}.size() > set<char>{begin(s2), end(s2)}.size(); }); auto conv = [] (string s, vector<char> const& m) { for(auto& c : s) { c = m[c - 'A']; } return s; }; string ans; function<void(int, vector<char>)> dfs = [&] (int i, vector<char> m) { if(ans == "-.") return; if(i == (int)ss.size()) { string tans = conv(ts[0], m); for(int j = 1; j < (int)ts.size(); ++j) { tans += " " + conv(ts[j], m); } tans += "."; if(!ans.empty() && ans != tans) { ans = "-."; } else { ans = tans; } return; } const auto& s = ss[i]; for(auto const& w : ws) { if(s.size() != w.size()) continue; bool check = true; vector<char> tm = m; for(int j = 0; j < (int)s.size(); ++j) { check &= m[s[j] - 'A'] == w[j] || (m[s[j] - 'A'] == '*' && m[w[j] - 'A'] == '*'); tm[s[j] - 'A'] = w[j]; tm[w[j] - 'A'] = s[j]; } if(!check) continue; dfs(i + 1, move(tm)); } }; dfs(0, vector<char>(26, '*')); cout << ans << endl; } }
AOJ 1307 - Towns along a Highway
解法
こういうのは確定できるところからさせるもの。
とりあえず一番遠いところは unique に定まるので確定させる。
次は、残ってる d の中で最も大きい値を選ぶ。
こいつは、明らかに端のどっちかと最も遠い位置関係にあるはず。
どっちと遠いかは 2 通りあるが、n <= 20 なので両方試す全探索が可能。
その座標に置いたときに、すでに確定させた位置との相対距離の集合が、残ってる d の集合の部分集合であればOKで、一旦それを消して次の探索に移る。
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n; while(cin >> n, n) { multiset<int, greater<>> d; for(int i = 0; i < n * (n - 1) / 2; ++i) { int x; cin >> x; d.insert(x); } vector<int> cur = {0, *d.begin()}; // x position d.erase(d.begin()); vector<vector<int>> ans; function<void(multiset<int, greater<>>&)> dfs = [&] (multiset<int, greater<>>& s) { if((int)cur.size() == n) { // ok ans.push_back({}); for(int i = 1; i < n; ++i) { ans.back().push_back(cur[i] - cur[i - 1]); } return; } auto attempt = [&] (int p) { vector<int> rm; for(auto x : cur) { const auto it = s.lower_bound(abs(p - x)); if(it == end(s) || *it != abs(p - x)) break; rm.push_back(*it); s.erase(it); } if(rm.size() == cur.size()) { cur.insert(lower_bound(begin(cur), end(cur), p), p); dfs(s); cur.erase(find(begin(cur), end(cur), p)); } s.insert(begin(rm), end(rm)); }; attempt(*s.begin()); attempt(cur.back() - *s.begin()); }; dfs(d); sort(begin(ans), end(ans)); ans.erase(unique(begin(ans), end(ans)), end(ans)); for(auto const& v : ans) { for(int i = 0; i < n - 1; ++i) { cout << v[i] << " \n"[i + 1 == n - 1]; } } cout << "-----" << endl; } }
感想
800点といわれて身構えてしまい、難しく考えすぎた。良くないね。
考察はわかりきったところから攻めていかないとなあ。
