第2回 ドワンゴからの挑戦状 予選: C - メンテナンス明け
https://beta.atcoder.jp/contests/dwango2016-prelims/tasks/dwango2016qual_c
問題概要
N個の駅とM個の路線が与えられる。各路線はLi個の駅を順につないだ単純パスになっており、各辺に移動時間が設定されている。駅srcから駅dstに向かいたいが、一度だけ寝過ごす可能性があり、寝過ごした場合は路線の終点まで強制的に移動する。一度寝過ごしたあとは二度と寝過ごすことはない。寝過ごしが任意の移動時に起こりうるとき、最大の移動時間を最小化するように移動したい。そのような場合の移動時間を求めよ。
N <= 25252
各路線に含まれる駅数の和 <= 252525
解法
二分探索をする。
- 必要な考察1. 仮に寝過ごしが発生した場合、寝過ごし後にたどり着く終点からdstまでは最小移動時間で行ける。またその最小移動時間はdstを始点にして1回ダイクストラを回せばすべての頂点に対して計算可能である。
- 必要な考察2. まだ寝過ごしが発生していない状態である辺を使って移動するとき、「仮にその移動で寝過ごしが発生した場合のdstまでの移動時間」は考察1より確定できる。
ここで「使っていい時間の最大値」を定めると、「もしある辺を使った移動で寝過ごしが起きたとき、移動時間が設定した最大値を超えるならばその辺を使うことはできない」ということが言える。よって二分探索の各ループではsrcから普通にダイクストラを回しつつ上の方法で禁止されない辺だけを使って移動していき、最終的にdstにたどり着けるかを見ればよい。
感想
あーすごい、こうやるのかというかんじ
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; void main() { immutable long INF = 1L << 59; auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto S = s[2]; auto T = s[3]; auto L = new int[](M); auto A = new int[][](M); auto W = new long[][](M); auto G = new Tuple!(int, long, int, long)[][](N); foreach (i; 0..M) { L[i] = readln.chomp.to!int; A[i] = readln.split.map!(to!int).array; W[i] = readln.split.map!(to!long).array; long acm1 = W[i].sum; long acm2 = 0; foreach (j; 0..L[i]-1) { acm2 += W[i][j]; G[A[i][j]] ~= tuple(A[i][j+1], W[i][j], A[i].back, acm1); G[A[i][j+1]] ~= tuple(A[i][j], W[i][j], A[i].front, acm2); acm1 -= W[i][j]; } } auto shortest = new long[](N); shortest.fill(INF); auto pq = new BinaryHeap!(Array!(Tuple!(int, long)), "a[1] > b[1]")(); auto dist = new long[](N); pq.insert(tuple(T, 0L)); while (!pq.empty) { auto t = pq.front; auto n = t[0]; auto d = t[1]; pq.removeFront; if (shortest[n] <= d) continue; shortest[n] = d; foreach (to; G[n]) { auto nn = to[0]; auto nd = d + to[1]; if (shortest[nn] <= nd) continue; pq.insert(tuple(nn, nd)); } } long hi = 10L^^15; long lo = 0; while (hi - lo > 1) { long mid = (hi + lo) / 2; dist.fill(INF); pq.clear(); pq.insert(tuple(S, 0L)); bool ok = false; while (!pq.empty) { auto t = pq.front; auto n = t[0]; auto d = t[1]; pq.removeFront; if (n == T) { ok = true; break; } if (dist[n] <= d) continue; dist[n] = d; foreach (to; G[n]) { auto nn = to[0]; auto nd = d + to[1]; auto zzz = to[2]; auto zzz_d = d + to[3]; if (zzz_d + shortest[zzz] > mid) continue; if (dist[nn] <= nd) continue; if (nd > mid) continue; pq.insert(tuple(nn, nd)); } } if (ok) hi = mid; else lo = mid; } hi.writeln; }
DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選: C - 特別講演「括弧列と塗り分け」
https://beta.atcoder.jp/contests/discovery2016-final/tasks/discovery_2016_final_c
問題概要
対応の取れた括弧列Sと非負整数Kが与えられる。Sの各文字を赤か青の2色で塗り分けるとき、すべての対応括弧の組(S[i], S[j])について、Sの区間[i, j]において赤と青の数の差がK以内になるような塗り方は何通りあるか。
|S|, K <= 3000
解法
木DPをした。括弧Aが括弧Bを包含しているときAがBの親となるようにすると、括弧の包含関係は木になる。また互いに包含関係にない括弧同士の塗り方は題意から独立である。このことから包含関係で木を作っていくと、1個以上の木（＝森）ができる。それぞれの木でDPを行った結果を掛け合わせれば答えとなる。具体的なDPは
dp(n, k): 構築した森のノードnにあたる括弧(S[i], S[j])において、Sの区間[i, j]を赤と青の差がk以下になるよう塗る塗り方の総数
を順に各ノードでやっていくわけだが、これはまず子のDP値を全部求めた上でそれを使ってノード内でDPをすると求まる。
各ノードでO(NK2)?っぽいDPをやるので全部でO(N2 K2)かかりそうな気がするが、最大でも区間長×2の差しか生まれない（それ以上のkは見る必要がない）ことに気を付けて適切に枝刈りを入れるとオーダーが落ちて通る。こういう感じの木DPにおける典型知識らしい→参照： http://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594
感想
気を付けず適切に枝刈りを入れなかったのでTLEを出しまくった
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; void main() { immutable long MOD = 10^^9 + 7; auto S = readln.chomp; auto N = S.length.to!int; auto K = readln.chomp.to!int; K = min(K, 2*N); auto P = new Tuple!(int, int)[](N/2); auto G = new int[][](N/2); auto root = new bool[](N/2); root.fill(true); long inv2 = powmod(2, MOD-2, MOD); auto stack = new Tuple!(int, int)[](N/2); for (int i = 0, p = 0, sp = -1; i < N; ++i) { if (S[i] == '(') { if (sp >= 0) G[stack[sp][1]] ~= p, root[p] = false; stack[++sp] = tuple(i, p++); } else { P[stack[sp][1]] = tuple(stack[sp][0], i); sp--; } } auto dp = new long[][](N/2, K+1); auto tmp = new long[][](2, N+1); void dfs(int n) { foreach (m; G[n]) dfs(m); int M = P[n][1] - P[n][0] + 1; tmp[0].fill(0); tmp[1].fill(0); tmp[0][0] = 2; tmp[0][1] = 2; int cur = 0, tar = 1; foreach (m; G[n]) { tmp[tar].fill(0); for (int i = 0; i <= M; ++i) { if (tmp[cur][i] == 0) continue; for (int j = 0; j <= K/2 && i+j <= M && dp[m][j] > 0; ++j) { (tmp[tar][i+j] += tmp[cur][i] * dp[m][j] % MOD * inv2 % MOD) %= MOD; } for (int j = 0; j <= K/2 && abs(i-j) <= M && dp[m][j] > 0; ++j) { (tmp[tar][abs(i-j)] += tmp[cur][i] * dp[m][j] % MOD * inv2 % MOD) %= MOD; } } swap(cur, tar); } for (int i = 0; i <= K/2; ++i) dp[n][i] = tmp[cur][i]; } long ans = 1; foreach (i; 0..N/2) { if (!root[i]) continue; dfs(i); long t = 0; foreach (j; 0..K/2+1) t = (t + dp[i][j]) % MOD; ans = ans * t % MOD; } ans.writeln; } long powmod(long a, long x, long m) { long ret = 1; while (x) { if (x % 2) ret = ret * a % m; a = a * a % m; x /= 2; } return ret; }
第2回 ドワンゴからの挑戦状 本選: B - 道迷い
https://beta.atcoder.jp/contests/dwango2016-honsen/tasks/dwango2016final_b
問題概要
一次元上のN個の点を表す数列Xが与えられる。このうちのいずれかの点がオフィスだが、その点がオフィスであるかどうかは実際に訪れるまでわからない。ここで座標0からスタートし一定の速度vで一次元上を動き回るとき、どこにオフィスがあった場合でも必ずabs(Xi)以下の時間でオフィスにたどり着くようにしたい。最適な移動をしたとき取りうる最小の速度vを求めよ。
N <= 1000
abs(Xi) <= 109
解法
問題の二分探索臭がすごいので二分探索を考える。そうすると解くべき問題は「速度vを決め打つ。速度vで最適に動き回ったとき、Xのすべての点に時間abs(Xi)以下でたどり着くことは可能か」となる。ここで移動の特性を考えると
- 点aから点bに移動したときa-b間にある点はすべてついでに取れる
- このことから移動のパターンは「必ず外側が広がっていくようにジグザグに移動する」しかない（飛び地での移動も既に訪れた区間の内部をまた訪れるのも無意味）
ということがわかる。これを生かすと以下の区間DPが生える。
dp(i, j, left_or_right): 区間[X_i, X_j]を訪れていて、最後に訪れたのが（区間の左端or区間の右端）のときの、最小移動距離
上の特性からこのdpは外側に広がって区間を伸ばすような遷移しか考える必要がない。すなわち遷移は（左端or右端）×（左端or右端）の以下4パターンとなる。
- X_i -> X_{i-1} （左端から左に一個進む）
- X_i -> X_{j+1} （左端から右に折り返して右端を一個広げる）
- X_j -> X_{i-1} （右端から左に折り返して左端を一個広げる）
- X_j -> X_{j+1} （右端から右に一個進む）
遷移の際現在決め打っている速度で新たな点Xに時間abs(X)以内で到達できない場合は題意が満たされずその遷移は取れないのでスルーする。最後までDPを埋めたときdp(0, N-1)にちゃんと値が入っていればその速度はok, としてにぶたんを回していく。
感想
最後は必ず端っこで終わる→ひとつ前はその端っこの隣もしくは逆の端っこ→その繰り返し… となるとつまりジグザグが広がっていく形か～→それyukicoderでやったやつじゃんとなって区間DPが生えた。時間かかったけど通せて良かった～なお虚無の定数倍高速化（言語を変える）をまたやってしまいました
コード (C++)
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i=0;i<(n);i++) #define REP2(i,m,n) for (int i=m;i<(n);i++) typedef long long ll; typedef long double ld; ll X[1010]; ll dp[1010][1010][2]; bool in_time(int i, long dist, ld vel) { return dist / vel <= abs(X[i]); } int main() { const ll INF = 1L << 59; int N; cin >> N; REP(i, N) cin >> X[i]; ld hi = 1000000000000000.0; ld lo = 1.0; REP(_, 100) { ld mid = (hi + lo) / 2; REP(i, N) REP(j, N) REP(k, 2) dp[i][j][k] = INF; REP(i, N) dp[i][i][0] = dp[i][i][1] = abs(X[i]); REP2 (len, 1, N+1) REP(l, N) REP(i, 2) REP(j, 2) { int r = l + len - 1; int nl = l; int nr = r; if (j == 0) nl -= 1; else nr += 1; if (nl < 0 || nr >= N) continue; if (i == 0 && j == 0) { ll nd = dp[l][r][i] + X[l] - X[nl]; if (in_time(nl, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd); } else if (i == 0 && j == 1) { ll nd = dp[l][r][i] + X[nr] - X[l]; if (in_time(nr, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd); } else if (i == 1 && j == 0) { ll nd = dp[l][r][i] + X[r] - X[nl]; if (in_time(nl, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd); } else if (i == 1 && j == 1) { ll nd = dp[l][r][i] + X[nr] - X[r]; if (in_time(nr, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd); } } if (min(dp[0][N-1][0], dp[0][N-1][1]) != INF) hi = mid; else lo = mid; } cout.precision(20); cout << fixed << hi << endl; }
第2回 ドワンゴからの挑戦状 本選: A - 通勤
https://beta.atcoder.jp/contests/dwango2016-honsen/tasks/dwango2016final_a
問題概要
ニコ数を「10進法で表記したとき各桁が2, 5のみからなり、かつどの隣り合う2桁の数字も相異なる数」と定義する。初め L=1, X=0 である。以下の2種類の操作を自由な順番で好きなだけ行ってXをNに一致させるとき、操作1を行う回数として最小のものを求めよ。
- 操作1: Lに任意のニコ数を掛ける
- 操作2: XにLを加算する。
N <= 10^{18}
解法
例えばN=123で、最初Lに5を掛ける場合を考える。いきなりLに5を掛けると、当然以降の加算は5の倍数刻みでしか行えなくなるため、X=123には永遠にたどりつけない。であるから、Lに5を掛ける前には、5で処理できない端数(123 % 5 = 3)をL=1の段階であらかじめ処理しておく必要がある。よってL=1を3回足してからLに5を掛けると、Nは残り120でL=5となる。実はこのとき両方をLで割って「Nは残り24でL=1」とみなしてしまって問題ない。このようにすると常にLが1に固定されてNがどんどんニコ数で割られていくという再帰的構造が現れるので、あとはメモ化再帰で解くことができる。Nが必ず2以上の数で割られるため状態数はそこまで増えない。
感想
再帰の構造を見出す部分がむじかった
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip, std.regex; void main() { immutable long INF = 10L^18+10; auto N = readln.chomp.to!long; long[] nico; for (long a = 2; a <= N; a = (a % 10 == 2) ? a * 10 + 5 : a * 10 + 2) nico ~= a; for (long a = 5; a <= N; a = (a % 10 == 2) ? a * 10 + 5 : a * 10 + 2) nico ~= a; auto M = nico.length.to!int; long[long] mem; long dfs(long n) { if (n in mem) return mem[n]; if (n == 1) return 1; if (n == 0) return 0; long ret = INF; foreach (x; nico) ret = min(ret, dfs(n/x) + n%x); mem[n] = ret; return mem[n]; } dfs(N).writeln; }
yukicoder No.529 帰省ラッシュ
https://yukicoder.me/problems/no/529
問題概要
N頂点M辺の単純無向連結グラフとQ個のクエリが与えられる。クエリには以下の2種類が存在する。クエリを順に実行した結果を出力せよ。
- クエリ1. 頂点uに価値wの獲物が出現する
- クエリ2. 頂点sからtに、同じ辺を2度以上通らないように移動する。このとき通った頂点にいる獲物を1匹だけ獲得することができる。獲得価値が最大になるように移動し、そのときの獲得価値を求めよ。獲得した獲物は以後消滅する。
N <= 105
M, Q <= 2×105
現れる獲物の価値はすべて異なる
解法
- 二重辺連結成分分解をする
- HL分解をする
- s, tのLCAをuとしたとき、s-u, t-uの経路に含まれる最大値をセグ木とかで取る
まず「同じ辺を2度通らない」という条件から、s->tへ向かうときは無関係の橋を通ってはいけない（戻ってこれなくなるため）。逆にそれ以外の橋は必ず決まった順序で通る必要がある。また現在地から橋を通らないで行ける1頂点に寄ってから次の橋へ（あるいはtへ）行くという動きを必ず取ることができる。以上よりクエリ2は「グラフを二重辺連結成分分解する。sを含む連結成分->tを含む連結成分 の単純パス上にある連結成分に含まれる頂点から、もっとも価値の大きい獲物をとる」と言い換えることができる。この言い換えを採用するとクエリ1の獲物追加も頂点単位ではなく連結成分単位で管理すればよいことになる。
上のとおりに二十辺連結成分分解を導入した場合、クエリ2に答える手順は「分解後のグラフ上でs->tへの単純パスを求める→通った連結成分におけるmaxをとる→maxだった獲物を削除する」となる。これを愚直にやると毎回O(N)かかって間に合わない。計算量の削減のためには二十辺連結成分分解後のグラフが必ず木になっていること、ゆえにs->tへの単純パスはs, tそれぞれからLCA(s, t)に向かう単純パスをつないだものであることに注目する。このようなクエリにはHL分解が有効で、木のパスをうまいこと分けてセグ木等と組み合わせることでmaxをとる計算量を抑えることができる（HL分解についてすごくわかりやすかったページ→ http://math314.hateblo.jp/entry/2014/06/24/220107 )
感想
とにかく実装が大変で競プロでひとつの問題に対して書いたコードとしてはダントツの量になった 途中でかなり意味が分からなくなって俺はいったい何で何を分解して何を求めてるんだ…みたいな状態になりオギャ～～～～～だった
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; alias Point = Tuple!(int, "x", int, "y", int, "i"); void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto Q = s[2]; auto G = new UndirectedGraph(N); foreach (_; 0..M) { s = readln.split.map!(to!int); G.add_edge(s[0]-1, s[1]-1); } G.bridge_decomposition; int gn = G.group_graph.length.to!int; auto T = new HLDecomposition(gn); foreach (i; 0..gn) { foreach (j; G.group_graph[i]) { T.add_edge(i, j); } } T.run(0); auto st = new SegmentTree(gn); auto W = new BinaryHeap!(Array!int, "a < b")[](gn); Tuple!(int, int) calc(int u, int v) { int un = T.nodes[u].serial; int ug = T.nodes[u].group; int vn = T.nodes[v].serial; int vg = T.nodes[v].group; Tuple!(int, int) ret; int g = vg; int last = vn; while (true) { if (g == ug && g == vg) { ret = max(ret, st.query(un, vn)); break; } else if (g == ug) { ret = max(ret, st.query(un, last)); break; } else { int g_root = T.groups[g].front; ret = max(ret, st.query(T.nodes[g_root].serial, last)); } int p = T.group_parent[g]; g = T.nodes[p].group; last = T.nodes[p].serial; } return ret; } while (Q--) { s = readln.split.map!(to!int); if (s[0] == 1) { int u = s[1] - 1; int w = s[2]; u = G.edge_group[u]; int un = T.nodes[u].serial; int ug = T.nodes[u].group; W[u].insert(w); st.assign(un, tuple(W[u].front, u)); } else { int u = s[1] - 1; int v = s[2] - 1; u = G.edge_group[u]; v = G.edge_group[v]; int w = G.lca_group(u, v); auto t = max(calc(w, u), calc(w, v)); auto maxw = t[0]; auto maxn = t[1]; writeln(maxw == 0 ? -1 : maxw); if (maxw > 0) { W[maxn].removeFront; } else { continue; } if (W[maxn].empty) { st.assign(T.nodes[maxn].serial, tuple(0, -1)); } else { st.assign(T.nodes[maxn].serial, tuple(W[maxn].front, maxn)); } } } } class UndirectedGraph { int N; int[][] G; int[][] dfs_tree; int[] dfs_subtree; bool[] dfs_subtree_odd; int[] ord; int[] low; int[] edge_group; int[][] group_graph; int[] depth; int[][] dp; bool lca_preprocessed = false; this (int N) { this.N = N; G = new int[][](N); } void add_edge(int u, int v) { G[u] ~= v; G[v] ~= u; } int[] articulation_points() { dfs_tree = new int[][](N); dfs_subtree = new int[](N); dfs_subtree_odd = new bool[](N); ord = new int[](N); low = new int[](N); auto used = new bool[](N); int cnt = 0; int dfs(int n, int p) { ord[n] = cnt++; low[n] = ord[n]; used[n] = true; foreach (m; G[n]) { if (m == p) continue; if (used[m]) low[n] = min(low[n], ord[m]); else low[n] = min(low[n], dfs(m, n)), dfs_tree[n] ~= m; } return low[n]; } int dfs2(int n, int p) { dfs_subtree[n] = 1; foreach (m; dfs_tree[n]) { if (m == p) continue; auto s = dfs2(m, n); if (s % 2) dfs_subtree_odd[n] = true; dfs_subtree[n] += s; } return dfs_subtree[n]; } int[] ans; foreach (i; 0..N) if (!used[i]) dfs(i, -1); foreach (i; 0..N) { if (ord[i] == 0 && dfs_tree[i].length >= 2) { ans ~= i; } else if (ord[i] != 0 && dfs_tree[i].map!(j => (low[j] >= ord[i])).any) { ans ~= i; } } foreach (i; 0..N) if (ord[i] == 0) dfs2(i, -1); return ans; } void bridge_decomposition() { auto uf = new UnionFind(N); edge_group = new int[](N); edge_group.fill(-1); int cnt = 0; articulation_points; void dfs(int n, int p) { foreach (m; dfs_tree[n]) { if (m != p && ord[n] >= low[m]) { uf.unite(n, m); } dfs(m, n); } } dfs(0, -1); /* foreach (i; 0..N) { foreach (j; G[i]) { if (i > j) continue; if (ord[i] < low[j]) continue; uf.unite(i, j); } } */ foreach (i; 0..N) { if (uf.table[i] < 0) { edge_group[i] = cnt++; } } group_graph = new int[][](cnt); foreach (i; 0..N) { edge_group[i] = edge_group[uf.find(i)]; } foreach (i; 0..N) { foreach (j; G[i]) { if (i > j) continue; if (edge_group[i] == edge_group[j]) continue; group_graph[edge_group[i]] ~= edge_group[j]; group_graph[edge_group[j]] ~= edge_group[i]; } } } void lca_pre() { void dfs(int n, int p, int d) { dp[0][n] = p; depth[n] = d; foreach (m; group_graph[n]) if (m != p) dfs(m, n, d+1); } int K = group_graph.length.to!int; depth = new int[](K); dp = new int[][](20, K); dfs(0, -1, 0); foreach (k; 0..19) foreach (n; 0..K) dp[k+1][n] = (dp[k][n] == -1) ? -1 : dp[k][dp[k][n]]; } int lca_group(int a, int b) { if (!lca_preprocessed) { lca_pre; lca_preprocessed = true; } if (depth[a] < depth[b]) swap(a, b); auto orig_a = a; auto orig_b = b; while (depth[a] > depth[b]) { int K = 19; foreach (k; iota(K, -1, -1)) { if (2^^k <= depth[a] - depth[b]) { a = dp[k][a]; K = k; } } } if (a == b) return a; while (dp[0][a] != dp[0][b]) { int K = 19; foreach (k; iota(K, -1, -1)) { if (dp[k][a] != dp[k][b]) { a = dp[k][a]; b = dp[k][b]; K = k; } } } return dp[0][a]; } } class UnionFind { int N; int[] table; this(int n) { N = n; table = new int[](N); fill(table, -1); } int find(int x) { return table[x] < 0 ? x : (table[x] = find(table[x])); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (table[x] > table[y]) swap(x, y); table[x] += table[y]; table[y] = x; } } class HLDecomposition { alias Node = Tuple!(int, "group", int, "number", int, "serial"); int N; int[][] G; int[][] groups; int[] parent; int[] group_parent; Node[] nodes; int[] serial_number; this (int N) { this.N = N; G = new int[][](N); nodes = new Node[](N); parent = new int[](N); } void add_edge(int u, int v) { G[u] ~= v; } void run(int root) { auto subtree_size = dfs_subtree_size(root); int group_count = -1; void decompose(int n, int p, bool heavy) { if (!heavy) { group_count += 1; groups.length += 1; group_parent ~= p; } parent[n] = p; nodes[n] = Node(group_count, groups[group_count].length.to!int, 0); groups[group_count] ~= n; bool first = true; G[n].sort!((a, b) => subtree_size[a] > subtree_size[b]); foreach (m; G[n]) { if (m == p) continue; decompose(m, n, first); first = false; } } decompose(root, -1, false); group_count += 1; int cnt = 0; foreach (g; groups) foreach (n; g) nodes[n].serial = cnt++; } int[] dfs_subtree_size(int root) { auto subtree_size = new int[](N); int dfs(int n, int p) { subtree_size[n] = 1; foreach (m; G[n]) if (m != p) subtree_size[n] += dfs(m, n); return subtree_size[n]; } dfs(root, -1); return subtree_size; } } class SegmentTree { Tuple!(int, int)[] table; int size; this(int n) { assert(bsr(n) < 29); size = 1 << (bsr(n) + 2); table = new Tuple!(int, int)[](size); } void assign(int pos, Tuple!(int, int) num) { return assign(pos, num, 0, 0, size/2-1); } void assign(int pos, Tuple!(int, int) num, int i, int left, int right) { if (left == right) { table[i] = num; return; } auto mid = (left + right) / 2; if (pos <= mid) assign(pos, num, i*2+1, left, mid); else assign(pos, num, i*2+2, mid+1, right); table[i] = max(table[i*2+1], table[i*2+2]); } Tuple!(int, int) query(int pl, int pr) { return query(pl, pr, 0, 0, size/2-1); } Tuple!(int, int) query(int pl, int pr, int i, int left, int right) { if (pl > right || pr < left) return tuple(0, -1); else if (pl <= left && right <= pr) return table[i]; else return max(query(pl, pr, i*2+1, left, (left+right)/2), query(pl, pr, i*2+2, (left+right)/2+1, right)); } }
AtCoder Grand Contest 022: C - Remainder Game
https://beta.atcoder.jp/contests/agc022/tasks/agc022_c
問題概要
N要素の数列A, Bがある。以下の操作を繰り返してAをBに一致させることができるかを判定せよ。可能ならば操作の最小コストも求めよ。
操作: 正整数kをひとつ選び、Aの各要素に対してそれぞれその要素をkで割った余りに変えるかそのままにするかを選ぶ。この一連の操作のコストは2k。
N <= 50 0 <= A, Bの各要素 <= 50
解法
まず重要な観察として、kに選ぶ数字は大きい数から降順で選んでいくと仮定してよい。例えば a < b として a, b の順で kを選んだ場合、aで余りを取った数は当然b未満になるため、bで余りをとることによる影響を及ぼせない。逆にb, aの順でkを選んだ場合には、bで余りを取った数はaで割ることによってさらに変化させられる可能性がある。ゆえにaを先に取る意味はない。さらにこのことからkで同じ数を2回以上選ぶ意味もないということがわかる。
以上より解の候補は 1～50 の数の集合として表すことができる。そのような集合のうち条件を満たすものの中で最小のコストを持つものが解となる。ある集合が条件を満たすかどうかはグラフの到達可能性問題として表すことができる。すなわち0～50のノードを持ったグラフに対して、「その集合に数xが含まれる場合ノードn → ノード(n%x) に辺を張る」というルールでグラフを構築すれば、ai -> biに到達可能かどうかで条件を満たすかどうかを判定できる。
またここでコストの計算方法より、x未満の数すべての集合で条件を満たすことができる場合、xを使うのは非最適である(21 + 22 + ... + 2x-1 < 2x)。ゆえに解の構築方法は以下のようになる。初め1～50のすべてを含む集合を持っておき、それを降順に見ていく。数xを見るときにはまずxを集合から外したうえで、その集合が条件を満たすかチェックする。仮にxを外しても条件を満たすのであれば上の事実よりxを使う必要はないので外したままにする。逆にxを外すと条件を満たさなくなる場合、xは必須であるので集合に戻す。これを繰り返して最終的に得られた集合が解である。
計算量はグラフの到達可能性の計算でO(N3), ひとつひとつの数を外してもいいかを見るとことでO(N)となりあわせてO(N4).
感想
最初がわからなかったから何をやってもだめ
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; void main() { immutable int M = 51; auto N = readln.chomp.to!int; auto A = readln.split.map!(to!int); auto B = readln.split.map!(to!int); auto S = iota(1, M).array; bool ok() { auto D = new int[][](M, M); foreach (i; 0..M) foreach (j; 0..M) D[i][j] = i == j ? 1 : 1 << 29; foreach (i; 0..M) foreach (j; S) D[i][i%j] = 1; foreach (i; 0..M) foreach (j; 0..M) foreach (k; 0..M) D[j][k] = min(D[j][k], D[j][i] + D[i][k]); return N.iota.map!(i => D[A[i]][B[i]] < 1 << 29).all; } if (!ok) { writeln(-1); return; } ulong ans = 0; foreach (i; iota(50, 0, -1)) { S = S.remove!(a => a == i); if (!ok) { S ~= i; ans += 1UL << i; } } ans.writeln; }
AtCoder Regular Contest 078: F - Mole and Abandoned Mine
https://beta.atcoder.jp/contests/arc078/submissions/2417009
問題概要
N頂点M辺の単純連結無向グラフが与えられる。このグラフから任意の辺集合を取り除いて頂点1から頂点Nまでの単純パスがただ1通りに定まるようにするとき、取り除く辺のコストの和の最小値を求めよ。
N <= 15
M <= N(N-1)/2
解法
取り除く辺のコストを最小化という問題は、一度すべての点を取り除いたあとで、加える頂点のコストを最大化する問題と言い換えることができる。こちらの方が都合が良いので以下ではこの言い換えた後の問題を解いていく。
まず頂点1から頂点Nまでの単純パスが1通りになるのは、パスに含まれる辺がすべて橋になっているときである。そのようなグラフの頂点は以下の2種類に分類できる。
- タイプ1. 1からNへの単純パスに含まれる頂点
- タイプ2. それ以外の頂点
ここで1からNへの単純パスが1通りという条件から、タイプ1の頂点からタイプ2の頂点を経由して別のタイプ1にたどりつくことはできない。逆にタイプ2の頂点からタイプ1の頂点に向かうとき、必ず最初にそれぞれの頂点ごとに決まったタイプ1の頂点を通る必要がある。つまりタイプ2の頂点はタイプ1のいずれかひとつの頂点に「属している」ような関係になっている。
ここでもしそれぞれの頂点のタイプが定まっており、さらに単純パスの形もタイプ2の頂点それぞれがどこに属しているかも定まっているとすると、題意を満たす最大の辺の張り方は一意に決定できる。まず単純パス上の辺はもちろん張る必要がある。次に各タイプ1の頂点について、「その頂点＋その頂点に属している頂点」の集合の中では張れるだけ辺を張っていい。逆にここで挙げた以外の辺は張ってはならない（張った瞬間単純パスが1通りであるという条件が満たされなくなる）。辺のコストに負はないので当然張れるだけ張るのが最適なやり方ということになる。
以上を前提とすると、以下のようなbitDPが立つ。
dp(mask, i): 頂点集合maskを既にグラフに取り込んでおり、最後に単純パス上に追加した頂点がiのときの最大コスト
このDPの遷移は「単純パスをひとつ伸ばす」「最後に単純パスに追加した頂点にタイプ2の頂点をくっつける」の2種類である。前者はまだ使ってない頂点を1個くっつけるだけなので普通のbitDPの遷移になる。後者の「タイプ2の頂点をくっつける」とは上で述べたとおり属する頂点を決めてその中で辺を張れるだけ張る処理のことである。これは前者の遷移と異なり複数の頂点が一度に追加されることもありうる。すなわちまだ使われてない頂点集合の、すべての部分集合が遷移先候補となる。部分集合の列挙を適当にやると2Nを全部列挙して部分になってるか判定の2N×2Nになってしまうが、ちゃんとやるテクでちゃんとやると全体で3Nに抑えられる（部分集合 列挙とかでググるといくつか出てくる）。あとは「その部分集合＋最後に単純パスにくっつけた頂点」の間で張れるだけの辺を張ったときのコストを足せばいいが、これは前計算しておけるのでDPの外でやっておく。
これでO(3N×N2)とかになるがdp(mask, i)のときiがmaskに含まれてないときとかは飛ばしたりすれば間に合う（解説だとO(3N×N)なんだけどちゃんと解析するとNが1個落ちたりするんだろうか
感想
どう見てもbitDPの見た目ではあるんだが全然組めなかった。解説を読んで一個一個イメージを積み重ねていくと確かにな～となって、すごいな～となった
コード (D言語)
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; void main() { immutable int INF = 1 << 29; auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto G = new int[][](N, N); foreach (_; 0..M) { s = readln.split.map!(to!int); G[s[0]-1][s[1]-1] = s[2]; G[s[1]-1][s[0]-1] = s[2]; } int cost_sum = 0; foreach (i; 0..N) foreach (j; i+1..N) cost_sum += G[i][j]; auto cost = new int[](1<<N); foreach (mask; 0..(1<<N)) { foreach (i; 0..N) { foreach (j; i+1..N) { if (!(mask & (1 << i))) continue; if (!(mask & (1 << j))) continue; cost[mask] += G[i][j]; } } } auto dp = new int[][](1<<N, N); foreach (i; 0..(1<<N)) dp[i].fill(-INF); foreach (i; 0..N) dp[1][0] = 0; auto masks = (1<<N).iota.array; masks.sort!((a, b) => a.popcnt < b.popcnt); foreach (mask; masks) { foreach (i; 0..N) { if (!(mask & (1 << i))) continue; foreach (j; 0..N) { if (mask & (1 << j)) continue; if (G[i][j] == 0) continue; dp[mask|(1<<j)][j] = max(dp[mask|(1<<j)][j], dp[mask][i] + G[i][j]); } int comp = (~mask) & ((1 << N) - 1); for (int U = (1 << N) - 1; U >= 0; --U) { U &= comp; dp[mask|U][i] = max(dp[mask|U][i], dp[mask][i] + cost[U|(1<<i)]); } } } int ans = cost_sum - dp[(1<<N)-1][N-1]; ans.writeln; }
