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] = []; } }
CODE FESTIVAL 2017 Elimination Tournament Round 1: D - Ancient Tree Record
https://atcoder.jp/contests/cf17-tournament-round1-open/tasks/asaporo2_d
問題概要
N頂点の木とN要素の数列Sが与えられる。木のすべての辺に整数の長さを割り当てて、Siが木の頂点iとすべての頂点との最短距離の和と等しくなるようにせよ。与えられる入力においてはそのような割り当て方がただひとつ存在することが保証される。
N <= 105
解法
ある頂点の組(a, b)を結ぶ辺eに注目すると、「Saの計算過程においてe以外の辺を通る回数」と「Sbの計算過程においてe以外の辺を通る回数」は等しい。また「Saの計算過程においてeを通る回数」はaから見てbの向こう側にある頂点の数に等しく、「Sbの計算過程においてeを通る回数」はbから見てaの向こう側にある頂点の数に等しい。よってSaとSbの差を取ったあと、eを通る回数の差でそれを割ればeの長さが一意に決定できる。
一点例外として、辺eの繋ぐ頂点(a, b)が両方とも木の中心である場合は注意が必要で、この場合SaもSbもeを通る回数も同じであるため上の方法では計算できない。しかしこの場合にも他のすべての辺は上の方法で求めることができるので、先にそれらを求めておけば残る辺eもそこから計算できる。
感想
なんか解けた、嬉しい 木の問題は辺を通る回数に着目するのが重要テクのひとつっぽいですね
コード (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() { auto N = readln.chomp.to!int; auto E = new Tuple!(int, int)[](N-1); auto G = new Tuple!(int, int)[][](N); foreach (i; 0..N-1) { auto s = readln.split.map!(to!int); G[s[0]-1] ~= tuple(s[1]-1, i); G[s[1]-1] ~= tuple(s[0]-1, i); E[i] = tuple(s[0]-1, s[1]-1); } auto S = readln.split.map!(to!long).array; if (N == 2) { writeln(S[0]); return; } auto depth = new int[](N); auto sub = new int[](N); auto ans = new long[](N-1); int dfs(int n, int p, int d) { depth[n] = d; foreach (m; G[n]) if (m[0] != p) sub[n] += dfs(m[0], n, d+1); return sub[n] + 1; } dfs(0, -1, 0); long dfs2(int n, int p, long d) { long ret = d; foreach (m; G[n]) if (m[0] != p) ret += dfs2(m[0], n, d+ans[m[1]]); return ret; } foreach (i, e; E.enumerate) { int a = e[0]; int b = e[1]; if (S[a] == S[b]) continue; if (depth[a] > depth[b]) swap(a, b); long aa = sub[b]; long bb = N - sub[b] - 2; ans[i] = (S[a] - S[b]) / (aa - bb); } foreach (i, e; E.enumerate) { int a = e[0]; int b = e[1]; if (S[a] != S[b]) continue; if (depth[a] > depth[b]) swap(a, b); long aa = dfs2(a, b, 0); long bb = dfs2(b, a, 0); long ss = aa + bb; ans[i] = (S[a] - ss) / (sub[b] + 1); } ans.each!writeln; }
CODE FESTIVAL 2016 Elimination Tournament Round 1: A - グラフ / Graph
問題概要
辺に正整数の重みが設定されたN頂点M辺の無向グラフと、Q個のクエリが与えられる。i個目のクエリでは頂点SiとTiが指定される。各クエリにおいて、「SiまたはTiを始点としたとき、集合に含まれる辺のみを使ってすべての頂点にたどりつくことができる」という条件を満たすように辺集合を選ぶとき、集合に含まれる辺の重みの和の最小値を求めよ。
N <= 4000
M <= 400000
Q <= 100000
解法
クエリ1回であれば最小全域森っぽいものを求めればいけそうだが、それを毎回計算するのは不可能である。ここで重要な発想はSiとTiを同一視して縮約しまうことである。このようにすると「SiまたはTi」という面倒な条件を考える必要がなくなり、単純に縮約後のグラフの最小全域木のコストはいくらになるか、という問題に言い換えることができる。
なおSiとTiを縮約するという操作はSi-Ti間にコスト0の辺を加えると言い換えてもここでは問題がない。後の見通しがよくなるのでここでは後者のやり方を取る。そうすると、各クエリで求める必要があるのは「元のグラフにSi-Ti間のゼロコスト辺を加えたグラフの最小全域木(のコスト)」である。これは各クエリで毎回愚直に求める必要はなく、最初に元のグラフの最小全域木さえ求めておけば簡単に求めることができる。具体的には元のグラフの最小全域木のSi-Ti間にゼロコスト辺を足す。そうするとひとつ辺が余るので取り除いて全体の重みを小さくすることができるようになる。ここで取り除くべき辺は、取り除いても連結のままになる辺のうち、コストがもっとも大きいものである。「取り除いても連結のままになる辺」は初めの最小全域木のうちSiとTiの間にある辺、つまりSi-Tiのパス上にあるいずれかの辺である。Nが小さいのでこれを毎クエリごとにO(N)で求めても十分間に合う。これでO(NQ)で解ける。
感想
縮約、結構現れるテクっぽい
コード (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; immutable long INF = 1L << 59; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto G = new Tuple!(int, long)[][](N); foreach (i; 0..M) { s = readln.split.map!(to!int); G[s[0]-1] ~= tuple(s[1]-1, s[2].to!long); G[s[1]-1] ~= tuple(s[0]-1, s[2].to!long); } long mst_cost = 0; auto H = new Tuple!(int, long)[][](N); auto P = new Tuple!(int, long)[](N); auto D = new int[](N); auto used = new bool[](N); auto q = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[2] > b[2]")(); q.insert(tuple(-1, 0, 0L)); while (!q.empty) { auto t = q.front; auto from = t[0]; auto cur = t[1]; auto d = t[2]; q.removeFront; if (used[cur]) continue; used[cur] = true; mst_cost += d; if (from != -1) { H[from] ~= tuple(cur, d); H[cur] ~= tuple(from, d); } foreach (m; G[cur]) { auto tar = m[0]; auto nd = m[1]; if (used[tar]) continue; q.insert(tuple(cur, tar, nd)); } } void dfs(int n, int p, long c, int d) { P[n] = tuple(p, c); D[n] = d; foreach (to; H[n]) if (to[0] != p) dfs(to[0], n, to[1], d+1); } dfs(0, -1, 0, 0); auto Q = readln.chomp.to!int; while (Q--) { s = readln.split.map!(to!int); auto a = s[0]-1; auto b = s[1]-1; if (D[a] > D[b]) swap(a, b); long maxv = -1; while (D[b] > D[a]) { maxv = max(maxv, P[b][1]); b = P[b][0]; } while (a != b) { maxv = max(maxv, P[a][1]); a = P[a][0]; maxv = max(maxv, P[b][1]); b = P[b][0]; } writeln(mst_cost - maxv); } }
CODE FESTIVAL 2016 Tournament Round 3: A - ストラックアウト / Struck Out
問題概要
1~Nまでの番号がついたN個のパネルがある。1度のゲームではK回ボールを投げてi回目にパネルjに当てるとi×Aj点が得られ、各回の点の和が得点となる。当てたパネルを順にP1, P2, ..., PK としたとき、1 <= P(i+1) - Pi <= M という条件の下でありうる最大の得点を求めよ。
N, M <= 105
K <= min(300, N)
解法
dp(i, j): i回目にパネルjに当てたときの最大の得点
とすると、dp(i, j) = max(dp(i-1, k) for k in (j-M)~(j-1)) である。セグ木をK本持てば普通にできそうだが、それだと O(KNlongN) で2秒には間に合わない。ここでjの小さいほうから順にdpを更新していく過程を見ていると、dp(i-1)から区間を横にずらしつつ最大値を取っていく形になっていることがわかる。このような場合スライド最小値(ここでは最大値だが)のやり方が使えて、これだと計算量がならしでO(N)になる。これでlogが落ちて答えが求まる。
おまけ:スライド最大値について(たぶん俺にしかわからないので蟻本2版p300を見てください)。
- まず両端キュー(deque)を用意する。
- このキューには値ではなくインデックスが入る
- このキューの並び順は、常に次の条件を満たす
- 左にあるものほど、そのインデックスが指す要素の値が大きい
- 要素の値の大きさが同じ場合は、左にあるものほどインデックス自体が小さい
- この条件が満たされている場合、区間の最大値は常にキューの左端に入っているインデックスを参照することでO(1)で得ることができる
- 既にキューがこの状態になっていると仮定して、区間を右にひとつずらすことを考えると
- まずずれた結果区間から外れたインデックスをキューから削除する。もしキューの左端を見て、そのインデックスがそれであればそのままpopする。そうでなければそのインデックスはもうキューの中にはないので何も操作する必要がない。
- 次に新しく加わるインデックスをキューに追加する。今度は右からキューを見ていって、キューが空になるかあるいはキューの右端インデックスの指す要素の値が新しいインデックスの要素の値より小さい間は右をpopし続ける。止まったらそこに新しいインデックスをpushする。
- 以上の操作では各インデックスについてpushとpopが高々1回ずつしか行われないので、ならしでO(N)となる
感想
まんまとlogをつけてTLEした。ゆきことか昔のABC-Dっぽい教育的問題感がある(スライド最小値名前だけ聞いてシカトしてたので勉強になった)。このくらい狙った設定じゃないとなかなかlog付きだけ落とすぞってのは難しそう
コード (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; immutable long INF = 1L << 59; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto K = s[2]; auto A = readln.split.map!(to!long).array; auto dp = new long[][](2, N); dp[0] = A.dup; int cur = 0, tar = 1; foreach (i; 1..K) { dp[tar].fill(-INF); auto q = new long[](2*N+10); int x = N/2; int y = N/2; foreach (j; i..N) { int a = j - M - 1; int b = j - 1; if (a >= 0 && x < y && q[x] == a) x++; while (x < y && dp[cur][q[y-1]] < dp[cur][b]) y--; q[y++] = b; dp[tar][j] = dp[cur][q[x]] + A[j] * (i + 1); } swap(cur, tar); } dp[cur].reduce!max.writeln; }