AOJ 1388 - Counting Cycles
解法
m <= n + 15 なので、サイクル基底を考えれば高々 2^16 通りしかないことがわかる。
つまり愚直にサイクルを探索しても、そこまで探索空間は大きくない。
サイクル空間を考えるにしろ、n, m が大きすぎるので、小さくしたい。
よく考えると、次数が 2 以下の頂点は縮約なり削除しても結果に影響しないことがわかる。
これによって、頂点数（辺の数）は k = m - n + 1 として 2k 程度に落ちることがわかる。
ここまで小さくなれば、愚直に探索しても十分間に合う。
注意点は以下の通り。
- 同じサイクルを重複して数えないようにする
- 残った辺に id を割り振って、使った辺集合を bit で管理して set に入れると楽
- 自己ループ、多重辺
- グラフ圧縮の過程で発生する
- 自己ループが発生してる頂点は変に削除すると数え漏れが起こるので注意（実装依存）
- 多重辺は、辺に固有 id を割り振っておいて区別すれば OK
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using graph = vector<set<pii>>; void compress_graph(graph& g, int& uid) { const int n = g.size(); queue<int> que; // remove leaves for(int v = 0; v < n; ++v) { if(g[v].size() == 1u) { que.push(v); } } while(!que.empty()) { const int v = que.front(); que.pop(); if(g[v].size() != 1u) continue; const auto e = *g[v].begin(); g[v].clear(); g[e.first].erase(make_pair(v, e.second)); if(g[e.first].size() == 1u) { que.push(e.first); } } // constraction for(int v = 0; v < n; ++v) { if(g[v].size() == 2u) { que.push(v); } } while(!que.empty()) { const int v = que.front(); que.pop(); if(g[v].size() != 2u) continue; const int a = g[v].begin()->first, a_uid = g[v].begin()->second; const int b = next(g[v].begin())->first, b_uid = next(g[v].begin())->second; if(a == b) continue; // self-loop g[v].clear(); g[a].erase(make_pair(v, a_uid)); g[b].erase(make_pair(v, b_uid)); ++uid; g[a].emplace(b, uid); g[b].emplace(a, uid); if(g[a].size() == 2u) { que.push(a); } if(g[b].size() == 2u) { que.push(b); } } map<int, int> eidx; graph tg(n); for(int v = 0; v < n; ++v) { for(auto& e : g[v]) { if(eidx.count(e.second) == 0) { const int id = eidx.size(); eidx[e.second] = id; } tg[v].emplace(e.first, eidx[e.second]); } } g = move(tg); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; graph g(n); int uid = 0; for(int i = 0; i < m; ++i) { int a, b; cin >> a >> b; a--, b--; g[a].emplace(b, uid); g[b].emplace(a, uid); uid += 1; } compress_graph(g, uid); set<ll> cycles; for(int s = 0; s < n; ++s) { if(g[s].empty()) continue; vector<bool> used_v(n); function<void(int, ll)> dfs = [&] (int v, ll used_edge) { used_v[v] = true; for(auto const& e : g[v]) { if(used_edge & (1LL << e.second)) continue; used_edge ^= 1LL << e.second; if(e.first == s) { cycles.insert(used_edge); used_edge ^= 1LL << e.second; continue; } if(!used_v[e.first]) { dfs(e.first, used_edge); } used_edge ^= 1LL << e.second; } used_v[v] = false; }; dfs(s, 0); } cout << cycles.size() << endl; }
感想
こういうのは本番では意外と通しにくい問題という印象がある。
AOJ 2686 - Unfair Game
解法
自明ケースからちょっとずつ難しくしていくのが良いと思った（実験しても良いかも）。
- a == b
同じ条件なので Nim (grundy 数) に帰着可能。
ある山の石の個数を s とすると s % (a + 1) が grundy 数なので（遷移を考えれば自明）、それの xor を取るだけ。
- a > b
さっきより先手有利。a == b のときに勝てるならOK。
基本的に a == b のときと同じように動くと考えれば、
もし a + 1 個以上ある山が1つでもあれば、全体 xor の値を好きな値にできるので、その時点で勝てる。
- a < b
a > b の逆で、先の条件を満たさない状態で後手に回せたらOK。
つまり 「a + 1 個以上ある山が1つ以下」「1 個以上 a 個以下とって全体 xor を 0 にできる」「取った結果、その山の個数は a 個以下になる」を満たすように取れたらOK。
ソースコード
#include <bits/stdc++.h> using namespace std; int grundy(vector<int> const& s, int a) { const int n = s.size(); int x = 0; for(int i = 0; i < n; ++i) { x ^= s[i] % (a + 1); } return x; } int main() { int n, a, b; cin >> n >> a >> b; vector<int> s(n); for(int i = 0; i < n; ++i) { cin >> s[i]; } const int max_v = *max_element(begin(s), end(s)); bool ans = false; if(a == b) { ans = grundy(s, a) != 0; } else if(a > b) { ans = max_v > b || grundy(s, b) != 0; } else { // a < b int cnt = 0; for(int i = 0; i < n; ++i) { cnt += s[i] > a; } // cnt >= 2 => lose if(cnt == 0) { ans = grundy(s, a) != 0; } else if(cnt == 1) { const int m = max_v % (a + 1); const int g = grundy(s, a) ^ m; if(g <= a) { const int take = (m - g + a + 1) % (a + 1); ans = take != 0 && max_v - take <= a; } } } cout << (ans ? "Hanako" : "Jiro") << endl; }
感想
ゲームは全部苦手だ。チームメイトが解いてくれるからサボりがちで良くないね。
AOJ 2250 - Operator
解法
二分探索やるだけじゃーんとなってサンプルチェックして違うことが判明するやつ。見事に引っかかってしまった。
良い性質がないか観察してみると、少なくとも可能かどうかの人数を効率よく見つけることはかなり難しい気がする。
ということは、人数を決め打ちしてシュミレートするしかないから、シュミレート部分を高速化するしかない。
というわけで考えたところ、O(N^2T) から落ちない。なんだこれ。
フラグが立っている先頭位置を高速に求められる bitset を持っていれば、定数倍で通せるなーとは思った。そういう問題なのかなーという気もしたけど、割と愚直にシミュレートしてもまあまあ早い気がした（？）のでそれで書く。
まず1秒毎すすめていく単純なシミュレートを考える。
時刻 t で電話に出られる人間の判定は t mod (l[i] + k[i]) <= l[i] となる i が分かれば良い。
オペレーターはいま出られる人数を普通に持っておいて、電話に出たら復活する位置にその数をインクリメントする。毎秒その時刻でよみがえる人を足し戻す。
電話に出る客が見つかったら、そいつを取り除いてやる。
まだ対応してない客の管理は list を使うと log がつかなくていい気がした。
削除が O(1) でできるから。set でもできるけど遅いし。bool の vector で毎回 O(n) チェックしても実は早いのかもしれない。
list を使うと客が減っていくに連れて探索が減るから若干早いことが期待できそうだなと思ってそうした。
これで O(N^2T) に多少の定数倍改善が入って何故か通った。なんもわからん。
実行時間は 0.3sec 程度。
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n, t; while(cin >> n >> t, n) { vector<int> m(n), l(n), k(n); for(int i = 0; i < n; ++i) { cin >> m[i] >> l[i] >> k[i]; } auto check = [&] (int num) { vector<int> restore(t + 1); list<int> ls; for(int i = 0; i < n; ++i) ls.push_back(i); int remain = num; for(int i = 0; i <= t; ++i) { remain += restore[i]; auto it = ls.begin(); while(remain > 0 && it != ls.end()) { const int idx = *it; if(i % (l[idx] + k[idx]) <= l[idx]) { --remain; if(i + m[idx] > t) return false; restore[i + m[idx]] += 1; it = ls.erase(it); } else { ++it; } } } return ls.empty(); }; for(int i = 1; i <= n; ++i) { if(check(i)) { cout << i << endl; break; } } } }
感想
公式解答見たら O(N^3 log) で定数倍早いから通るとかいってて笑った。
ICPC とはいっても、今でもこんな問題出せるのかは怪しい気がする。
list を使ったのは久々だなあ。
NEERC 2010 K - Graph Oddity
問題概要
n 頂点 m 辺の単純で連結な無向グラフが与えられる。n は奇数である。
deg(v) を頂点 v の次数とし、k を deg(v) の最大値以上で最小の奇数と定義する。
このとき、グラフを k 色以下で頂点彩色せよ。
・制約
3 <= n <= 9999
1 <= m <= 100000
n は奇数
解法
n と k が両方奇数なので、k 色以下で塗る方法は必ず存在することが示せる。
次数の大きい方からとっていくだけだとうまくいかない。
そこで、以下のアルゴリズムを考える。
- S をすべての頂点からなる集合とする
- S が空でないなら、S で deg(v) が最小のものを取り出し、v とする
- 配列 ord の末尾に v を追加
- v の隣接頂点の次数をデクリメントする
- 2 に戻る
このとき、ord[i] について以下の不変条件が成り立つ。
「頂点 ord[i] は、j < i なる任意の頂点 ord[j] に色が塗られていなければ、ほかはどのように彩色されていても、ある色で塗ることができる」
以下、大雑把な証明。
- deg(ord[i]) < k ならば、そもそも好きに色をぬることができる。
- deg(ord[i]) = k となることはない。もし成り立つとすると ord[i] の隣接頂点は一度も v として選ばれておらず、deg(u) = k (u は隣接頂点) が成り立つ。同様に u の隣接頂点も選ばれていないから…と議論が続き、結局この段階では ord[i] 以外の任意の頂点が選ばれていないことになる。すなわち、G は完全グラフである。k が奇数なので、G は偶数個の頂点を含むが、これは矛盾である。
よって、あとは ord[i] の逆順に色を適当に塗っていけばうまくいく。
要は自由に塗れるやつは後回しにする、という発想でしかない。
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int main() { ifstream ifs("kgraph.in"); int n, m; ifs >> n >> m; vector<vector<int>> g(n); vector<int> deg(n); int k = 0; for(int i = 0; i < m; ++i) { int a, b; ifs >> a >> b; a--, b--; g[a].push_back(b); g[b].push_back(a); deg[a] += 1; deg[b] += 1; k = max({k, deg[a], deg[b]}); } k += k % 2 == 0; set<pii> s; // (deg, v) vector<int> ord(n); for(int v = 0; v < n; ++v) s.emplace(deg[v], v); for(int i = 0; i < n; ++i) { const int v = s.begin()->second; s.erase(s.begin()); ord[i] = v; for(auto to : g[v]) { if(s.count(make_pair(deg[to], to))) { s.erase(make_pair(deg[to], to)); deg[to]--; s.emplace(deg[to], to); } } } vector<int> ans(n, -1); for(int i = n - 1; i >= 0; --i) { const int v = ord[i]; vector<bool> used(k + 1); for(auto to : g[v]) { if(ans[to] == -1) continue; used[ans[to]] = true; } for(int j = 1; j <= k; ++j) { if(!used[j]) { ans[v] = j; break; } } } ofstream ofs("kgraph.out"); ofs << k << '\n'; for(int i = 0; i < n; ++i) { ofs << ans[i] << '\n'; } }
AOJ 2861 RPG Maker
解法
典型構築だと思われる。
4n - 1, 4m - 1 であることが重要で、この制約のためにすべてのマスを回収するようなパスが存在する。
イメージとしては蛇のようにうねうねしながら移動するというもの。
あとは実装を楽にするだけ。とりあえず始点を無視して (0, 0) から始める。
とりあえず (0, 0) -> (h-1, 0) へ一直線に移動する。
その後は蛇のように上に上がっていくと、いずれ (0, 0) にたどり着く。
こうしてできたパスはループになる。
あとは、'@' の位置が始点になるようにパスをずらし (rotate する)、末尾にある余計な移動を削除すればよい。
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int main() { int h, w; cin >> h >> w; vector<string> s(h); int sy = -1, sx = -1; for(int i = 0; i < h; ++i) { cin >> s[i]; for(int j = 0; j < w; ++j) { if(s[i][j] == '@') { sy = i, sx = j; } } } vector<pii> path; for(int i = 0; i < h; ++i) { path.emplace_back(i, 0); } function<void(int, int, int)> snake = [&] (int y, int x, int dx) { path.emplace_back(y, x); if(x + 2 * dx == 0 && y == 0) { path.emplace_back(0, 1); return; } if(x + dx < 2 || w <= x + dx) { path.emplace_back(y - 1, x); dx *= -1; y -= 2; snake(y, x, dx); } else { snake(y, x + dx, dx); } }; snake(h - 1, 1, 1); rotate(begin(path), find(begin(path), end(path), make_pair(sy, sx)), end(path)); while(s[path.back().first][path.back().second] != '*') { path.pop_back(); } for(auto const& p : path) { const int y = p.first, x = p.second; if(s[y][x] == '.') { s[y][x] = '#'; } } for(auto const& t : s) { cout << t << endl; } }
感想
焦ると実装が沼になりそう。落ち着いて処理したい。
AOJ 1382 Black or White
解法
いかにも DP の高速化をする見た目をしている。
DP を考える前に、操作を観察する。
色々実験などして考えてみると、
- ある位置を3回以上塗るのは最適ではなさそう
- 2つの区間を違う色で塗る時、それらは互いに全く交わらないか、一方がもう一方を完全に内包している
ことがわかる。特に2つ目が本質である。
例えば [0, 5] を B で、[2, 7] を W で塗る操作を考えてみれば、これは [0, 1] を B でぬり、[2, 7] を W で塗る操作と同値である。
つまり、考える必要があるのは、ある区間を一色で塗ったときに、その区間を目的の色にするのに最小何手かかるか、ということである。
結論を言えば、B を W が交互にあらわれる（つまり B と W の境界）個数を２で割って切り上げたものが最小手数である。
例えば、WWWWWW を WBWBWB にしたいとする。仮に全体を B で塗って BBBBBB としよう。すると、ここから目的の色にするためには、独立して現れる W の数だけ塗るのが最適である。この数が、"WB" または "BW" となる位置の数（今回なら、5 箇所ある）を２で割って切り上げた数に等しい。
こうして、DPを考えるに必要な情報が揃った。
今、
dp[i] := i 文字目までみて最小手数はいくらか
sum[i] := i までみて、W と B の境界は何回現れるか
と定義する。sum は累積和で予め計算しておく。
すると遷移は
- s[i - 1] == t[i - 1] のとき：dp[i] = dp[i - 1]
- s[i - 1] != t[i - 1] のとき： dp[i] = min(dp[j] + ceil((sum[i] - sum[j + 1]) / 2) + 1) (i - k <= j < i)
となる。２つ目の遷移で +1 しているのは、注目区間を t[i - 1] 一色で塗る操作の分である。
この状態だと O(nk) なので、高速化する。２つ目の遷移式を整理すると
- dp[i] = ceil(min((2 * dp[j] + sum[i] - sum[j + 1]) / 2) + 1) (i - k <= j < i)
となり、min の j に依存している部分は 2 * dp[j] - sum[j + 1] だけであるから、この部分だけ取り出して、適切なデータ構造 (deque や segment tree) で管理すると良い。
実装例は deque でスライド最小値しており、 O(n) である。
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int main() { int n, k; cin >> n >> k; string s, t; cin >> s >> t; vector<int> sum(n + 1); for(int i = 0; i < n; ++i) { sum[i + 1] = sum[i] + (i == 0 || t[i - 1] != t[i]); } vector<int> dp(n + 1); deque<pii> deq; deq.emplace_back(0, -1); for(int i = 1; i <= n; ++i) { if(deq.front().first < i - k) deq.pop_front(); if(s[i - 1] == t[i - 1]) { dp[i] = dp[i - 1]; } else { dp[i] = (deq.front().second + sum[i] + 1) / 2 + 1; } if(i != n) { const int added = 2 * dp[i] - sum[i + 1]; while(!deq.empty() && deq.back().second >= added) deq.pop_back(); deq.emplace_back(i, added); } } cout << dp[n] << endl; }
感想
これめっちゃ嘘が生えそうな形をしていて本番だと怖い。サンプルも強くないし。
AOJ 1622 Go around the Labyrinth
解法
右手法かフロー（最大流）で解けるが、今回はフローで解く。
フロー解は割と一発ネタなところがある。
まず、各マスを2つの頂点に倍化（入力ノード、出力ノード）し、これら2つの頂点の間に辺をはる。
このときのコストは、4隅以外は1、4隅は2とする。
また、隣接マスの間に、コスト1の無向辺を張る。出力ノードから入力ノードに張ること。
こうして作ったグラフをコピーして2つ用意し、g1, g2 とする。
g1 における左上から右下への最大流が2であり、かつ、g2 における左下から右上への最大流が2であるとき、"YES" となる。
これでうまくいくのは、直感的には、4つの disjoint なパスを重ね合わせたときに、パスの外周を回るように移動すれば実現できるからである。
N, M <= 50 のグリッドグラフなのでフローでも間に合う。
右手法だと N, M <= 1000 とかでも解けるが、フロー解は実装で失敗するところが皆無なので、どっちを選択するかは好みの問題かもしれない。
ソースコード
#include <bits/stdc++.h> using namespace std; template <typename Edge> class graph { using graph_t = std::vector<std::vector<Edge>>; public: using reference = std::vector<Edge>&; using const_reference = std::vector<Edge> const&; using iterator = typename graph_t::iterator; using const_iterator = typename graph_t::const_iterator; using reverse_iterator = typename graph_t::reverse_iterator; graph() : g() {} graph(int n) : g(n) {} reference operator[](int x) { return g[x]; } const_reference operator[](int x) const { return g[x]; } iterator begin() { return std::begin(g); } const_iterator begin() const { return std::begin(g); } iterator end() { return std::end(g); } const_iterator end() const { return std::end(g); } reverse_iterator rbegin() { return std::rbegin(g); } reverse_iterator rend() { return std::rend(g); } int size() const { return g.size(); } void add_node(std::vector<Edge> es) { g.push_back(std::move(es)); } private: std::vector<std::vector<Edge>> g; }; template <typename Capacity> struct capacity_edge { using capacity_type = Capacity; int to, rev; capacity_type cap; capacity_edge(int t, int r, capacity_type c) : to(t), rev(r), cap(c) {} }; template <typename Capacity> using capacity_graph = graph<capacity_edge<Capacity>>; template <typename Capacity> void add_edge(capacity_graph<Capacity>& g, int from, int to, Capacity cap) { g[from].emplace_back(to, static_cast<int>(g[to].size()), cap); g[to].emplace_back(from, static_cast<int>(g[from].size() - 1), Capacity{0}); } template <typename Edge, typename Capacity = typename Edge::capacity_type> Capacity augument(graph<Edge>& g, std::vector<bool>& used, int v, int t, Capacity f) { if(v == t) return f; used[v] = true; for(auto& e : g[v]) { if(!used[e.to] && e.cap > 0) { auto d = augument(g, used, e.to, t, std::min(f, e.cap)); if(d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; } } } return 0; } template <typename Edge, typename Capacity = typename Edge::capacity_type> Capacity max_flow(graph<Edge>& g, int s, int t) { Capacity flow = 0; std::vector<bool> used(g.size(), false); while(true) { std::fill(std::begin(used), std::end(used), false); const auto f = augument(g, used, s, t, std::numeric_limits<Capacity>::max() / 2); if(f == 0) return flow; flow += f; } } constexpr int dx[4] = {0, 1, 0, -1}; constexpr int dy[4] = {1, 0, -1, 0}; int main() { int n, m; while(cin >> n >> m, n) { vector<string> s(n); for(int i = 0; i < n; ++i) { cin >> s[i]; } capacity_graph<int> g1(2 * n * m); auto in_range = [&] (int y, int x) { return 0 <= y && y < n && 0 <= x && x < m; }; for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { if((i == 0 && j == 0) || (i == 0 && j == m - 1) || (i == n - 1 && j == 0) || (i == n - 1 && j == m - 1)) { add_edge(g1, i * m + j, i * m + j + n * m, 2); } else { add_edge(g1, i * m + j, i * m + j + n * m, 1); } if(s[i][j] == '#') continue; for(int k = 0; k < 4; ++k) { const int ny = i + dy[k], nx = j + dx[k]; if(!in_range(ny, nx) || s[ny][nx] == '#') continue; add_edge(g1, i * m + j + n * m, ny * m + nx, 1); } } } auto g2 = g1; if(max_flow(g1, 0, (n - 1) * m + m - 1) == 2 && max_flow(g2, (n - 1) * m, m - 1) == 2) { cout << "YES" << endl; } else { cout << "NO" << endl; } } }
