第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; }
yukicoder No.584 赤、緑、青の色塗り
https://yukicoder.me/problems/no/584
問題概要
1×Nのグリッドを以下のルールを守って赤、緑、青で彩色するとき、ありうる塗り方は何通りか。
- R個のマスが赤、G個のマスが緑、B個のマスが青になるようにし、残りのマスは未彩色のまま残す
- 3マス以上連続して色が塗られないようにする
- 2マス以上連続して同じ色が塗られないようにする
N <= 3000
解法
正しい塗り方をすると、最終的には「2マス連続で色が塗られている箇所」「1マスだけ色が塗られている箇所」が空白マスに区切られて並んでいる形になる。
まず「2マス連続で色が塗られている箇所」が何個あるかを決めると、「1マス孤立して色が塗られている箇所」が何個あるかが決まり、さらに空白マスが何個残るかも決まる。その上でこれらの並べ方が何個あるかを考えると、「2マス」と「1マス」をそれぞれ空白の間に挿し込んでいく形になるので、(空白の数+1)C(「2マス」の数+「1マス」の数）となる。
次に並べたマスに色を塗っていくことを考える。まず赤の塗り方であるが、赤を「2マス」に何個塗って「1マス」に何個塗るかは総当たりする必要がある。なぜならどちらのマスに塗ったかによって次の色に残されるマス数が変わってくるからである（1マスの方に塗った場合は別の色で塗れない）。
こうして赤を塗ったあとは「2マス（片方が赤で塗られている）」「2マス（両方塗られていない）」「1マス（塗られていない）」の3種類のマスが残ることになる。ここに緑を塗っていくことを考えると、まず「2マス（両方塗られていない）」には必ず緑を塗る必要がある（そうしないと青で両方を塗ることになってしまう）。ゆえに緑の塗り方の総数は（「2マス（片方が赤で塗られている）」＋「1マス（塗られていない）」）から （B－「2マス（両方塗られていない）」）を選ぶ総数となる。残った青の塗り方はここまでの手続きで自動的に1通りに定まるので考慮する必要はない。
以上より、最初の2マス・1マスの取り方を総当たりするのにO(N), 赤の塗り方を総当たりするのにO(N)かかるのでO(N2)で答えが出せる。コンビネーションは前計算しておく。
感想
めっちゃ泥臭いが、一歩一歩解法を詰めていける感じで良かった
コード (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 MAX = 4000; immutable long MOD = 10^^9+7; auto modinv = new long[](MAX); modinv[0] = modinv[1] = 1; foreach(i; 2..MAX) { modinv[i] = modinv[MOD % i] * (MOD - MOD / i) % MOD; } auto f_mod = new long[](MAX); auto f_modinv = new long[](MAX); f_mod[0] = f_mod[1] = 1; f_modinv[0] = f_modinv[1] = 1; foreach(i; 2..MAX) { f_mod[i] = (i * f_mod[i-1]) % MOD; f_modinv[i] = (modinv[i] * f_modinv[i-1]) % MOD; } long comb(int n, int k) { if (n < k) return 0; return f_mod[n] * f_modinv[n-k] % MOD * f_modinv[k] % MOD; } auto s = readln.split.map!(to!int); auto N = s[0], R = s[1], G = s[2], B = s[3]; auto M = max(R, G, B); auto RGB = R + G + B; long ans = 0; foreach (two; 0..RGB/2+1) { auto one = RGB - two * 2; auto emp = N - two * 2 - one; if (M > two + one) continue; if (emp + 1 < one + two) continue; long tmp1 = comb(emp+1, one) * comb(emp+1-one, two) % MOD; foreach (i; max(0, R-one)..min(R, two)+1) { long tmp2 = tmp1 * comb(two, i) % MOD * comb(one, R-i) % MOD; int one_rest = one - (R-i); int two_rest = two - i; if (G < two_rest) continue; tmp2 = tmp2 * comb(one_rest + i, G - two_rest) % MOD; tmp2 = tmp2 * powmod(2, two, MOD); ans = (ans + tmp2) % 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; }
yukicoder No.96 圏外です。
https://yukicoder.me/problems/no/96
問題概要
N個の中継局が二次元平面上の相異なる整数座標上に存在する。中継局と中継局は距離10以下であれば通信でき、無線機と中継局、無線機と無線機は距離1以下であれば通信できる。加えて、同じ中継局と通信できるもの同士も通信することができる。2次元平面上の任意の位置に2つの無線機を通信できるように置くとき、2つの無線機の間の距離の最大値を求めよ。
N <= 120000
-10000 <= Xi, Yi <= 10000
解法
- 手順1. 通信できる中継局を1つのグループにまとめる
- 手順2. 各グループの中で最遠点対を求める
まず手順1では距離が10以下という条件を満たす中継局同士をUnionFind等でまとめていく。ただし単純にすべての組の距離を求めているとO(N2)で間に合わない。ここで見るべき距離が10以下と小さいことを生かすと、ひとつの中継局においてはx, yが高々-10～10の正方形の範囲に存在する中継局との距離だけを調べれば十分であることがわかる。これは各中継局をx座標ごとにバケット分けした上で各バケットをy座標でソートしたりしておけば、二分探索でO(NlogN)でできる（具体的には(x-10)～(x+10)のバケットそれぞれにおいて、二分探索で(y-10)以上の最初の点を見つけて、y+10を超えるまで順に距離を確かめるという手順をとればよい。中継局は整数座標かつ相異なるという条件が効いているので、実際に距離を確かめる回数はひとつの中継局につき最大でも20×20回程度に抑えられる）。
手順2では手順1で求めたグループごとに最遠点対を割り出し、その最大距離を求める。やり方としては各グループで凸包を作ってその中の点対を総当たりすればよい。x, yの取りうる範囲が狭いこと、整数座標しかありえないことから凸包はそんなに大きくならず、凸包内で二乗の総当たりをしても十分間に合う。最後に無線機2台分の距離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; void main() { auto N = readln.chomp.to!int; auto P = N.iota.map!(_ => readln.split.map!(to!int)).map!(a => Point(a[0], a[1])).array; if (N == 0) { writeln(1); return; } Tuple!(int, int)[][int] X; foreach (i, p; P.enumerate) { X[p.x] ~= tuple(p.y, i.to!int); } foreach (k; X.keys) X[k].sort(); auto uf = new UnionFind(N); foreach (i, p; P.enumerate) { foreach (dx; -10..11) { int nx = p.x + dx; if (nx !in X) continue; int j = X[nx].assumeSorted.lowerBound(tuple(p.y, 0)).length.to!int; for (int k = j; k < X[nx].length; ++k) { int ny = X[nx][k][0]; if (dx * dx + (ny - p.y) * (ny - p.y) > 100) break; if (nx != p.x || ny != p.y) uf.unite(i.to!int, X[nx][k][1]); } for (int k = min(j, X[nx].length.to!int-1); k >= 0; --k) { int ny = X[nx][k][0]; if (dx * dx + (ny - p.y) * (ny - p.y) > 100) break; if (nx != p.x || ny != p.y) uf.unite(i.to!int, X[nx][k][1]); } } } int farest = 0; foreach (i; 0..N) { if (uf.groups[i].empty) continue; auto ch = convex_hull(uf.groups[i].map!(i => P[i]).array); foreach (j; 0..ch.length) { foreach (k; j+1..ch.length) { farest = max(farest, dist2(ch[j], ch[k])); } } } writefln("%.9f", sqrt(farest * 1.0L) + 2); } struct Point { int x; int y; } Point[] convex_hull(Point[] points) { int N = points.length.to!int; points.sort!((a, b) => a.x == b.x ? a.y < b.y : a.x < b.x); Point[] ch1, ch2; foreach (i; 0..N) { while (ch1.length >= 2 && rot(ch1[$-2], ch1[$-1], points[i]) <= 0) ch1.popBack; ch1 ~= points[i]; } foreach_reverse (i; 0..N) { while (ch2.length >= 2 && rot(ch2[$-2], ch2[$-1], points[i]) <= 0) ch2.popBack; ch2 ~= points[i]; } auto ch = ch1 ~ ch2; return ch.sort!((a, b) => a.x == b.x ? a.y < b.y : a.x < b.x).uniq.array; } int rot(Point a, Point b, Point c) { // a -> b -> c の向き // 正なら左、負なら右、0なら同一直線状 return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } int dist2(Point a, Point b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); } class UnionFind { int N; int[] table; int[][] groups; this(int n) { N = n; table = new int[](N); fill(table, -1); groups = new int[][](N); foreach (i; 0..N) groups[i] = [i]; } 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; groups[x] ~= groups[y]; groups[y] = []; } }
