Atcoder ABC 031 D. 語呂合わせ
Atcoder ABC 031 D. 語呂合わせ
D: 語呂合わせ - AtCoder Beginner Contest 031 | AtCoder
解法
各数字が表す文字列$\ s_j\ $の長さに関する全探索をする。それぞれの文字列の情報$\ i\ $に対して、$\ \sum_{j = 0}^k |s_j| = |w_i|\ $を満たすかどうかを判定し、満たすならばそれぞれの数に対する文字列が一意に定まる。すべての情報に関してすべて矛盾がないかをsetやvectorなどを用いて確認して、問題なければそれを出力すると良い。
全探索は3進数を使って管理した。その3進数を$\ s\ $としたとき、下から$\ i\ $番目の数字を見るには、$\ \lfloor \frac {s} {3 ^ i} \rfloor (mod\ 3)\ $を見ればよい。
実装
#include "bits/stdc++.h" using namespace std; int main() { int k, n; cin >> k >> n; vector<string> v(n), w(n); for (int i = 0; i < n; i ++) cin >> v[i] >> w[i]; for (int s = 0; s < pow(3, k); s ++) { vector<int> len(k); for (int i = 0; i < k; i ++) len[i] = ((int)(s / pow(3, i)) % 3) + 1; vector<string> ans(k, ""); for (int i = 0; i < n; i ++) { int len_sum = 0; for (int j = 0; j < v[i].size(); j ++) len_sum += len[v[i][j] - '0' - 1]; if (len_sum != w[i].size()) goto next; string next = w[i]; for (int j = 0; j < v[i].size(); j ++) { int p = len[v[i][j] - '0' - 1]; string get = next.substr(0, p); next = next.substr(p); if (ans[v[i][j] - '0' - 1] != "" && ans[v[i][j] - '0' - 1] != get) goto next; ans[v[i][j] - '0' - 1] = get; } } for (int i = 0; i < ans.size(); i ++) cout << ans[i] << endl; break; next:; } return 0; }
Atcoder AGC 010 F. Tree Game
Atcoder AGC 010 F. Tree Game
F: Tree Game - AtCoder Grand Contest 010 | AtCoder
この点数の問題を完全に自力で通せたので驚いた。こういうタイプの問題が得意になってきた（気がする）ので嬉しい。思考の流れもまとめて記述しておく。まぁ順位表見てもわかるように、さすがに1600点の難易度ではない。
解法
まず、自分が移動させた結果、$\ a = 0\ $であるような頂点に移動した場合、勝ちである。また「周囲の頂点がすべて$\ a > 1\ $であり、かつ$\ a = 1\ $であるような頂点」に移動した場合も、同様に勝ちである。なぜなら、次の自分の番にまたその頂点に戻ってくることが可能だからである。
より一般的に、「周囲の頂点がすべて$\ a > k\ $であり、かつ$\ a = k\ $であるような頂点」に移動した場合も勝ちである。上と同様に、それ以降常に相手の動きの逆の動きをとればよい。
ここまでの考察で、今いる頂点$\ v\ $から移動するべき頂点$\ u\ $は、$\ a_v > a_u\ $を満たすような頂点のみであることが推測でき、それは実際正しい。なぜなら、仮に$\ a_v \leq a_u\ $となる頂点に移動することで自分が有利になるのだとしたら、相手はその方向に行かせないようにするはずなので、$\ a_u\ $から$\ a_v\ $に戻るような手を打つはずである。このとき、両方の$\ a\ $の値が$\ 1\ $ずつ減少するが、大小関係は変わらないので、これを繰り返しても負けることになるだけである。よってこのような移動はする意味がない。
以上の考察で、常に$\ a\ $が小さくなるような遷移を繰り返していくことで、決着がつくことが示された。実装を簡単にするために、そもそも$\ a_v < a_u\ $を満たすようなところにのみ$\ a_u\ $から$\ a_v\ $に向かって有向辺を張っておけばよい。これでそのまま遷移先をすべて考えることができる。
勝敗の判定は普通にやればよい。すなわち、まず行き先がそれ以上ない場合は、$\ lose\ $の状態である。行き先がある場合は、その行き先のいずれかに$\ lose\ $の状態があるならばそこに移動すればよいので$\ win\ $、すべて$\ win\ $となってるときはどう動いても負けるので$\ lose\ $とすればよい。
$\ O(n)\ $。なぜ$\ 2 \leq n \leq 3000\ $なのかがいまいちわからない。
実装
#include "bits/stdc++.h" using namespace std; vector<int> a; vector<vector<int>> g; vector<bool> win; vector<bool> used; bool dfs(int v) { used[v] = true; if (g[v].size() == 0) return win[v] = false; bool lose = true; for (int u : g[v]) lose &= dfs(u); return win[v] = !lose; } int main() { int n; cin >> n; a.resize(n); g.resize(n); win.resize(n); used.resize(n, false); for (int i = 0; i < n; i ++) cin >> a[i]; for (int i = 0; i < n - 1; i ++) { int u, v; cin >> u >> v; u --, v --; if (a[u] == a[v]) continue; if (a[u] > a[v]) g[u].push_back(v); else g[v].push_back(u); } for (int i = 0; i < n; i ++) if (!used[i]) dfs(i); for (int i = 0; i < n; i ++) if (win[i]) cout << i + 1 << ' '; return 0; }
AOJ Slim Span
AOJ Slim Span
解法
まず全域木の中で、重みが最小となる辺を固定する。その重み以上辺のみを使って、$Kruskal$法によって最小全域木を作り、その時の$Slimness$を求め、その最小値をとる。
辺はあらかじめ重みで昇順にソートしておけば、順番に辺を選んでいくだけでよいことになる。計算量は一応$\ O(m^2)\ $。
実装
#include "bits/stdc++.h" using namespace std; #define all(x) x.begin(), x.end() struct UnionFind { int n; vector<int> parent; vector<int> rank; vector<int> num; int find(int x) { if (parent[x] == x) return x; return parent[x] = find(parent[x]); } UnionFind(int n_) { n = n_; parent.resize(n); for (int i = 0; i < n; i ++) parent[i] = i; rank.assign(n, 0); num.assign(n, 1); } void unite(int x, int y) { if ((x = find(x)) != (y = find(y))) { if (rank[x] < rank[y]) { parent[x] = y; num[y] += num[x]; } else { parent[y] = x; if (rank[x] == rank[y]) rank[x] ++; num[x] += num[y]; } n --; } } bool same(int x, int y) { return find(x) == find(y); } int get() { return n; } int get(int x) { return num[find(x)]; } }; struct edge { int a, b, c; edge(int a, int b, int c) : a(a), b(b), c(c) { } }; static const int INF = 0x3f3f3f3f; int main() { int n, m; while (cin >> n >> m && n) { vector<edge> es; for (int i = 0; i < m; i ++) { int a, b, c; cin >> a >> b >> c; a --, b --; edge e(a, b, c); es.push_back(e); } sort(all(es), [](const edge &a, const edge &b) { return a.c < b.c; }); int ans = INF; for (int i = 0; i < m; i ++) { int cnt = 0; UnionFind uf(n); for (int j = i; j < m; j ++) { if (uf.same(es[j].a, es[j].b)) continue; uf.unite(es[j].a, es[j].b); cnt ++; if (cnt == n - 1) { ans = min(ans, es[j].c - es[i].c); break; } } } if (ans == INF) ans = -1; cout << ans << endl; } return 0; }
Atcoder ARC 080 E. Young Maids
Atcoder ARC 080 E. Young Maids
E: Young Maids - AtCoder Regular Contest 080 | AtCoder
解法
ある区間（最初は全体）の数列の偶数番目（$0-indexed$）の最小値と、その最小値より右側にあって、かつその数を基準に数えて、奇数番目にあるような数の最小値をとってくる、ということを繰り返せば題意の数列が求められる。
これらの数が位置$\ l\ $と$\ r\ $からとられたならば、次考える区間は、$\ [0, l),\ [l + 1, r),\ [r + 1, n)\ $である。これらを分割統治的にやっていくためには、キューを使えばよいが、次に取り出したい区間は、（その区間における偶数番目の数の最小値）が最小になるものであるから、そのように取り出せるように優先度付きキューを用意すればよい。さらに、区間の最小値を高速に求める必要があるので、当然セグメント木などを利用する。時間計算量は$O(n\log n)$。
実装
#include "bits/stdc++.h"; using namespace std; #define OUT(x) cerr << #x << " = " << x << endl; #define all(x) x.begin(), x.end() #define mp make_pair #define pii pair<int, int> #define piii pair<int, pair<int, int>> static const int INF = 0x3f3f3f3f; template<typename Type> struct SegmentTree { vector<Type> data; int n; SegmentTree(int x) { n = pow(2, ceil(log2(x))); data.resize(2 * n - 1); for (int i = 0; i < 2 * n - 1; i ++) data[i] = mp(INF, i - n + 1) ; //初期値 } Type merge(Type x, Type y) { //更新関数 if (x.first < y.first) return x; else return y; } void update(int k, int p) { //k番目をpで更新する k += n - 1; data[k].first = p; while (k > 0) { k = (k - 1) / 2; data[k] = merge(data[k * 2 + 1], data[k * 2 + 2]); } } // [l, r) Type query(int a, int b) { return query(a, b, 0, 0, n); } Type query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return mp(INF, -1); //初期値 if (a <= l && r <= b) return data[k]; int m = (l + r) / 2; return merge(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r)); } }; int main() { int i, j; int n; cin >> n; vector<int> p(n); for (i = 0; i < n; i ++) cin >> p[i]; SegmentTree<pii> st_even(n), st_odd(n); for (i = 0; i < n; i ++) { if (i & 1) st_odd.update(i, p[i]); else st_even.update(i, p[i]); } priority_queue<piii, vector<piii>, greater<piii>> pq; pq.push(mp(st_even.query(0, n).first, mp(0, n))); vector<int> ans(n); int ansi = 0; while (!pq.empty()) { piii get = pq.top(); pq.pop(); pii segment = get.second; int a, b; pii get1, get2; if (segment.first & 1) get1 = st_odd.query(segment.first, segment.second); else get1 = st_even.query(segment.first, segment.second); a = get1.second; ans[ansi ++] = get1.first; if (a & 1) get2 = st_even.query(a, segment.second); else get2 = st_odd.query(a, segment.second); b = get2.second; ans[ansi ++] = get2.first; if (segment.first < a) { if (segment.first & 1) pq.push(mp(st_odd.query(segment.first, a).first, mp(segment.first, a))); else pq.push(mp(st_even.query(segment.first, a).first, mp(segment.first, a))); } if (a + 1 < b) { if ((a + 1) & 1) pq.push(mp(st_odd.query(a + 1, b).first, mp(a + 1, b))); else pq.push(mp(st_even.query(a + 1, b).first, mp(a + 1, b))); } if (b + 1 < segment.second) { if ((b + 1) & 1) pq.push(mp(st_odd.query(b + 1, segment.second).first, mp(b + 1, segment.second))); else pq.push(mp(st_even.query(b + 1, segment.second).first, mp(b + 1, segment.second))); } } for (i = 0; i < n; i ++) cout << ans[i] << (i == n - 1 ? '\n' : ' '); return 0; }
Atcoder ABC 069 A. K-City
Atcoder ABC 069 A. K-City
A: K-City - AtCoder Beginner Contest 069 | AtCoder
解法
$(n - 1) (m - 1)$を出力するだけ。$O(1)$。
実装
#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; cout << (n - 1) * (m - 1) << endl; return 0; }
Atcoder AGC #018 F. Two Trees
Atcoder AGC #018 F. Two Trees
F: Two Trees - AtCoder Grand Contest 018 | AtCoder
頂点数が等しい根付き木が２つ与えられる。この木の各ノードに対して、値を割り当てることを考える。ただしノード番号が同じものは同じ値を割り当てる。任意の部分木（根を含む）について、それが含む各頂点に割り当てられた値の総和の絶対値が１に等しくなるような、値の割り当て方が存在するかどうか、そして存在するならばその一例を示すという問題。
半分自分で考え、半分解説に頼った。まず、条件を満たす方法によって、あるノードに値が割り当てられているならば、その値は、そのノードの子（子孫ではなく）の数の偶奇と一致していてはいけない。なぜならば、条件より、その子以下からなる根付き木について、その総和は＋１か−１のどちらかであるので、子ノードが一つ増えるということは、総和の偶奇が反転するということであるからである。さらにこのことより、各ノードの子の数の偶奇はどちらの木においても同じであることが必要である。もう一つ気づかなければならないことは、割り当てる値を必要以上に大きくしなくてよいことである。どこの部分木の和をとってもその絶対値が１を超えないようにすればよいので、総和に関しても、割り当てる値に関しても、-1, 0, 1以外の値を取らせなくてよい。このことから、各ノードに対して、その子の数を数えることで、その偶奇に応じて、0を割り当てるか、1 or -1を割り当てるかを決めることができる。1 or -1の部分を部分木内でマッチングさせて、あとでマッチングされたもの同士が1と-1になるようにうまく割り当てる。このとき、2つの木の両方で条件を満たすように割り当てなければならないので、このマッチングさせたもの同士が辺で結ばれた新しいグラフを用意し、そこで隣り合うもの同士を別の色で塗ることを考えれば、すべてうまく割り当てることができる。閉路ができることもあるが、長さが偶数なので、問題ない。
#include "bits/stdc++.h" using namespace std; vector<int> g[2][101010]; vector<int> gg[202020]; vector<int> ans; int used[101010]; int dfs(int v, int k, vector<vector<int>> &zero) { vector<int> matching; //ノードvを根とする部分木の中で、マッチングさせたいものをいれる if (!zero[k][v]) matching.push_back(v); for (int u : g[k][v]) { int get = dfs(u, k, zero); if (get == -1) continue; matching.push_back(get); } if (g[k][v].size() == 0) return (zero[k][v] ? -1 : v); while (matching.size() >= 2) { //２個ずつてきとうにマッチングさせて良い int s1 = matching.back(); matching.pop_back(); int s2 = matching.back(); matching.pop_back(); gg[s1].push_back(s2); gg[s2].push_back(s1); } if (matching.size() == 1) return matching[0]; //余った場合はマッチングさせたいノード番号を返す else return -1; //これ以上マッチングさせるものはない } void coloring(int v, int w) { used[v] = true; ans[v] = w; for (int u : gg[v]) if (!used[u]) { coloring(u, -w); //1と-1を交互に塗る } } int main() { int n, a; cin >> n; vector<int> root(2); for (int k = 0; k < 2; k ++) { for (int i = 0; i < n; i ++) { cin >> a; if (a == -1) { root[k] = i; } else { a --; g[k][a].push_back(i); } } } vector<vector<int>> zero(2, vector<int> (n, false)); for (int k = 0; k < 2; k ++) { for (int i = 0; i < n; i ++) { if (g[k][i].size() & 1) zero[k][i] = true; } } bool ok = true; for (int i = 0; i < n; i ++) ok &= zero[0][i] == zero[1][i]; if (!ok) { cout << "IMPOSSIBLE" << endl; return 0; } for (int k = 0; k < 2; k ++) dfs(root[k], k, zero); ans.resize(n, 0); for (int i = 0; i < n; i ++) { if (!zero[0][i] && !used[i]) { coloring(i, 1); } } cout << "POSSIBLE" << endl; for (int i = 0; i < n; i ++) cout << ans[i] << (i == n - 1 ? '\n' : ' '); return 0; }
Atcoder AGC #015 C. Nuske vs Phantom Thnook
Atcoder AGC #015 C. Nuske vs Phantom Thnook
C: Nuske vs Phantom Thnook - AtCoder Grand Contest 015 | AtCoder
実はグラフの問題だったという感じがして好きな問題。
色が塗られたグリッドが与えられる。その上下左右について辺を共有するマス同士を連結であると呼ぶと、連結な部分については、木のようになっている。このとき、長方形を表すクエリに対して、その中に何個の連結成分があるかを答えていく問題。愚直に数えていては当然間に合わないので、累積和を使うことは多分みんな思いつく。が、そこからが長かった。次の森の性質に気付けるかが重要であった（そもそも木であることになんの意味があるのか数時間気づけなかった）。
森に関して、その連結成分の数をu, 辺の数をm, 頂点の数をnとすると、n - m = vとなる。
木について辺の数がn - 1であることを考えれば割と自明ではある。というか問題が解けた後に気付いたんだけど。
このことを利用すると、長方形が与えられた時に、累積和を用いてその中に含まれる塗られたグリッドの総数（頂点数nの個数に相当する）を求め、さらにその中に含まれる塗られたグリッド同士を仕切る部分の総数（辺の数mに相当する）を求めることで、連結成分の個数が求められる。
グラフ理論しっかりやりたい感が強くなった。
#include "bits/stdc++.h" using namespace std; int main() { int h, w, q; cin >> h >> w >> q; vector<string> s(h); for (int i = 0; i < h; i ++) cin >> s[i]; vector<vector<int>> t(h, vector<int> (w)); for (int i = 0; i < h; i ++) { for (int j = 0; j < w; j ++) { if (s[i][j] == '1') t[i][j] = 1; else t[i][j] = 0; } } vector<vector<int>> ver(h, vector<int> (w, 0)); vector<vector<int>> hor(h, vector<int> (w, 0)); for (int y = 0; y < h; y ++) { for (int x = 0; x < w; x ++) { if (x + 1 < w) if (t[y][x] && t[y][x + 1]) hor[y][x] = 1; if (y + 1 < h) if (t[y][x] && t[y + 1][x]) ver[y][x] = 1; } } for (int x = 0; x < w; x ++) { for (int y = 1; y < h; y ++) { t[y][x] += t[y - 1][x]; ver[y][x] += ver[y - 1][x]; hor[y][x] += hor[y - 1][x]; } } for (int y = 0; y < h; y ++) { for (int x = 1; x < w; x ++) { t[y][x] += t[y][x - 1]; ver[y][x] += ver[y][x - 1]; hor[y][x] += hor[y][x - 1]; } } while (q --) { int y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2; y1 --, x1 --, y2 --, x2 --; int sum = t[y2][x2] - (y1 - 1 >= 0 ? t[y1 - 1][x2] : 0) - ((x1 - 1 >= 0 ? t[y2][x1 - 1] : 0) - (y1 - 1 >= 0 && x1 - 1 >= 0 ? t[y1 - 1][x1 - 1] : 0)); int versum = 0; y2 --; if (y1 <= y2) { versum = ver[y2][x2] - (y1 - 1 >= 0 ? ver[y1 - 1][x2] : 0) - ((x1 - 1 >= 0 ? ver[y2][x1 - 1] : 0) - (y1 - 1 >= 0 && x1 - 1 >= 0 ? ver[y1 - 1][x1 - 1] : 0)); } y2 ++; int horsum = 0; x2 --; if (x1 <= x2) { horsum = hor[y2][x2] - (y1 - 1 >= 0 ? hor[y1 - 1][x2] : 0) - ((x1 - 1 >= 0 ? hor[y2][x1 - 1] : 0) - (y1 - 1 >= 0 && x1 - 1 >= 0 ? hor[y1 - 1][x1 - 1] : 0)); } x2 ++; cout << sum - versum - horsum << endl; } return 0; }
