全国統一プログラミング王決定戦予選 / NIKKEI Programming Contest 2019: E - Weights on Vertices and Edges
https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e
問題概要
N頂点M辺の連結な無向グラフが与えられる。グラフの各頂点と各辺には重みが設定されている。辺をひとつ選んでグラフから削除するという操作を何回でも行えるとき、削除されていないすべての辺について、その辺の重みがその辺の属する連結成分の全頂点の重みの総和を超えないという条件が満たされた状態するために最小何本の辺を削除する必要があるか求めよ。
N, M <= 105
解法
明らかに重い辺ほど削除対象になりやすいことを考えると、以下のようなステップで問題を解くことができる。
- まだ削除もマークもされていない中で最大の重みを持つ辺を見る。
- その辺が条件を満たしていないならば、削除する。
- その辺が条件を満たしているならば、その辺が属する連結成分のすべての辺は必ず条件を満たす。なのでそのような辺をすべて残存確定としてマークする。
- 削除もマークもされていない辺がなくなるまで1に戻ってこれを繰り返す。
これをそのまま実装しようとすると、辺の削除とそれに伴う連結成分の分割が必要になるが、そのような操作は基本的に難しい。なのでこの類の操作を要求される問題でよく用いられるテクニックである「操作を逆順で考える」をやる。つまりはじめは辺が全部削除された状態で頂点だけがあり、だんだん辺が追加されていく、というような形である。辺を追加して連結成分をくっつけていく操作はUnionFindのようなデータ構造で簡単に行えるため、こちらの方が操作もしやすく見通しがよい。
上の操作を逆順にやる場合、軽い辺から順に繋いでいくことになるが、上に書いたことをそのままやることは難しい。特にステップ3の他の辺を残存確定とするところが邪魔で、これを逆操作で再現するのはどうにも無理っぽい感じがする(逆から見ていく以上、その辺が残存確定になっているかどうかは知りようがないため)。なので逆操作をしやすくするために、上の操作を少し言い換える。具体的には毎ステップ必ず削除を行うようにして、逆操作における追加操作と対応がつくようにする。手順としては以下のようになる。
- まだ見ていない中で最大の重みの辺を見る。
- その辺が条件を満たしているならば、その辺が属する連結成分のすべて辺は必ず条件を満たす。なのでそのような辺をすべてマークする。
- その辺を 必ず 削除する。ただしその辺がマークされている場合、最終的な答えの削除数にはカウントしない。
- すべての辺を見るまでこれを繰り返す。
このようにすると毎回辺の削除が行われるので逆操作との対応がつきやすくなる。これに基づいた逆操作は以下のようになる。
- まだ見ていない中で最小の重みの辺を見る。
- その辺を繋げる。つまり辺が頂点(u, v)間を繋ぐとき、uの属する連結成分とvの属する連結成分をひとつの連結成分にまとめる。この操作は元の操作における削除に対応しているため、コストに+1を加算する。
- 辺の重みがこれによってできた連結成分内の全頂点の重みの総和未満である場合、この時点でこの連結成分に属している辺はすべて条件を満たす。よってそれらすべての辺の削除はなかったことにできるので、それらすべての辺によって足されたコストを無効にする。
- すべての辺を見るまでこれを繰り返す。
実装上ではUnionFindの各連結成分にコストを持たせておくと管理しやすい(uniteするときはコストを足す、無効にするときはゼロにする、というようにすると最終的にひとつの連結成分になったときのコストが答えになる)。
感想
アルメリアさんのツイートを見て解けました
解法はなんかどう書いても天下り的な感じになってしまってむずかしい おもいつきたいね
コード (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, core.stdc.string; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto X = readln.split.map!(to!long).array; auto G = new Tuple!(int, long)[][](N); auto E = new Tuple!(int, int, long)[](M); 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); E[i] = tuple(s[0]-1, s[1]-1, s[2].to!long); } E.sort!"a[2] < b[2]"; auto uf = new UnionFind(N, X); foreach (e; E) { uf.unite(e[0], e[1]); int u = uf.find(e[0]); if (uf.weights[u] >= e[2]) { uf.unused_edges[u] = 0; } } int u = uf.find(0); uf.unused_edges[u].writeln; } class UnionFind { int N; int[] table; long[] weights; long[] unused_edges; this(int n, long[] X) { N = n; table = new int[](N); fill(table, -1); weights = new long[](N); foreach (i; 0..N) weights[i] = X[i]; unused_edges = new long[](N); } 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 (table[x] > table[y]) swap(x, y); unused_edges[x] += 1; if (x == y) return; weights[x] += weights[y]; unused_edges[x] += unused_edges[y]; table[x] += table[y]; table[y] = x; } }
AtCoder Grand Contest 016: D - XOR Replace
https://atcoder.jp/contests/agc016/tasks/agc016_d
問題概要
長さNの数列A, Bが与えられる。Aの要素をひとつ選びその値をAのすべての要素のXORで置き換えるという操作を好きなだけ行えるとき、AをBに一致させることができるか判定せよ。また可能な場合には最小の操作回数も求めよ。
N <= 105
解法
初期状態でのA全体のXORを仮にXと置く。このときXOR演算の性質から、仮にA[2]をXで置き換えたあとのA全体のXORはA[2]になる( x xor y xor z = w <=> w xor y xor z = x )。よって次にA[3]を選んだ場合、A[3]は初期状態のA[2]と置き換えられる。そして今度はA[3]がA全体のXORになる。このように、一度操作を行うとそのとき選んだ要素が次の「A全体のXOR」になるということがわかる。
なのでこの問題で行っている操作は結局単純なswapであるといえる。つまり初期状態でのA全体のXORをAの末尾にくっつけた数列A'を考えたとき、A'において末尾以外の要素と末尾をswapしているのとまったく同じことである。単なるswapなので当然操作の過程で新たな数が登場したりすることもない。よって一致可能性判定はかなり簡単にできて、Bに対しても末尾に全体のXORをくっつけた数列B'を考えたときにA'とB'の構成要素が同じかどうかを見ればよい。
これで一致させられるかどうかの判定はできたので、あとは最小操作回数を求めることになる。先程言い換えたようなswap操作で考えると、効率の良い一致のさせ方は「今の末尾にある数を、それを必要としている場所に送り込む -> 新たに末尾に入ってきた数を、それを必要としている場所に送り込む -> ...」という風に、玉突き的に値がずれていく感じの操作になる。別の言い方をすると、好きな順番でいくつかの要素(末尾は必ず含む)を選択し、選択した順で値をcyclic shiftさせるような操作をすると、最低限の操作回数で複数の値を一気に一致させることができる、ということになる。ただしこのとき注意しなくてはいけないのが「末尾は必ず含む」のところで、末尾の値が必要なかったとしても必ずシフトに巻き込まれることになってしまい、1回分余計に操作をする必要が生じる。以下で具体例を見ていく。
たとえばA'が{1, 2, 3, 0}でB'が{2, 3, 1, 0}だったとき、操作は {1, 2, 3, 0} -> {1, 2, 0, 3} -> {1, 3, 0, 2} -> {2, 3, 0, 1} -> {2, 3, 1, 0} と4回になる。{2, 3, 0, 1}の時点でcyclic shiftが完了しているのだが、末尾の0はもともとずれていた数の集合{1, 2, 3}には含まれていないので、それを元の位置に戻すために操作を+1回行っている。n個の要素のcyclic shiftには(n-1)回の操作が必要で今回はさらに+1回操作をしているため、結局4回の操作になった。
一方で{1, 2, 3}を{2, 3, 1}に一致させることを考えると、これは {1, 2, 3} -> {1, 3, 2} -> {2, 3, 1} と2回で済む。これは末尾の数が必要とされていたためで、このような場合はcyclic shiftを1回やるだけで各要素がぴったりはまるので、操作は(n-1)回で済む。
また別のパターンの例としてA'が{1, 2, 3, 4, 5, 1}でB'が{2, 3, 1, 5, 4, 1}のときを考える。このとき明らかに (1, 2, 3) と (4, 5) は別々にcyclic shiftを行っていくべきで、(1, 2, 3)の方は末尾の1のおかげで最後の合わせ+1回が必要ないが、(4, 5)の方は最後の+1回が必要となる。
上のようなパターンだと見て明らかに(1, 2, 3)と(4, 5)は別だとわかるが、一般的に解くためにはもう少し定式的にやる必要がある。どのようにやるかというと、A[i]!=B[i]となるiがあったとき、A[i]とB[i]をそれぞれグラフの頂点番号とみなして(A[i], B[i])間に辺を張ることにする。これをA', B'のすべてのi(0 <= i <= N)に対して行って出来たグラフにおいて、同じ連結成分内に属するものの集合をひとつのcyclic shiftの単位とみなすことができる(詳しい話は公式解説等参照)。連結成分だけが問題であるので実際にはグラフをつくる必要はなく、UnionFindとかで連結成分を管理すればよい(頂点番号が大きくなりうるので座標圧縮的なテクであらかじめ値を潰しておくとかはする必要がある)。
各連結成分内で必要な操作回数は、上で述べたように末尾の数を必要とするかどうかによって違いがあり、もし末尾と関わりのない連結成分であれば(要素数+1)回かかる。なおここでいう要素数はUnionFindで持ったときの要素数ではなく、その連結成分にA[i]が含まれており、かつA[i]!=B[i]であるようなiの数であることに注意する(グラフをつくる段階で同じ値の要素をひとつの頂点に潰してしまっているのでここは一致しない)。末尾と関わりのあるような連結成分であれば+1が必要なく単に要素数回の操作になる。ただしこのときA'の末尾!=B'の末尾であれば、それは要素数に含めなくてよい。なぜならここが等しくてもそうでなくても必ずcyclic shiftには巻き込まれるからで、さらに連結成分の性質からcyclic shiftの結果どちらにせよB'の末尾に等しい値が移動してくることがわかっているからである。
以上をまとめると、結局A[i]!=B[i]であるような箇所は末尾を除いて答えに+1の寄与があり、さらに末尾と関わりのない連結成分の数だけ余計な操作が+1されるので、この数をかぞえて足せば答えとなる。
感想
今回ばかりは本当に意味のわからない文章を書いてしまった手応えがあるので自分が解くとき参考にしたリンクを張りまくって逃げます
http://kmjp.hatenablog.jp/entry/2017/06/25/0900
https://camypaper.bitbucket.io/2017/06/20/agc016d/
https://www.hamayanhamayan.com/entry/2017/06/19/185428
https://kimiyuki.net/writeup/algo/atcoder/agc-016-d/
https://www.youtube.com/watch?v=kdQtQSgIYPI (解説放送)
コード (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, core.stdc.string; void main() { auto N = readln.chomp.to!int; auto A = readln.split.map!(to!int).array; auto B = readln.split.map!(to!int).array; A ~= A.reduce!((a,b) => a^b); B ~= B.reduce!((a,b) => a^b); if (A.dup.sort() != B.dup.sort()) { writeln(-1); return; } auto C = A.dup.sort().uniq.array; int M = C.length.to!int; int[int] D; foreach (i; 0..M) { D[C[i]] = i; } A.each!((ref a) => a = D[a]); B.each!((ref a) => a = D[a]); auto uf = new UnionFind(M); foreach (i; 0..N+1) { if (A[i] != B[i]) { uf.unite(A[i], B[i]); uf.edge[uf.find(A[i])] += 1; } } int ans = 0; foreach (i; 0..M) { if (uf.find(i) != i) continue; if (uf.edge[i] == 0) continue; if (uf.find(A.back) == i) { ans += uf.edge[i]; if (A.back != B.back) ans -= 1; } else { ans += uf.edge[i] + 1; } } ans.writeln; } class UnionFind { int N; int[] table; int[] edge; this(int n) { N = n; table = new int[](N); fill(table, -1); edge = new int[](N); } 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); edge[x] += edge[y]; table[x] += table[y]; table[y] = x; } }
AtCoder Regular Contest 041: D - 辺彩色
https://atcoder.jp/contests/arc041/tasks/arc041_d
問題概要
N頂点M辺の無向グラフが与えられる。このグラフの各辺を以下のルールに従って赤か青のどちらかで塗っていくとき、各辺を初めに指定されている色で塗ることができるか判定せよ。
ルール: 自由に始点を選び、隣接頂点に移動することを繰り返す。奇数回目の移動で通った辺を赤、偶数回目の移動で通った辺を青で塗る。このとき古い色は新しい色で上書きされる。
N, M <= 2000
解法
操作を逆順にして終点→始点の移動を考えると、彩色が「最後に通ったときの色」ではなく「最初に通ったときの色」になる。つまり上書きという条件を消して考えることができるようになる。このようにすると一度通った辺を逆戻りすることなどが好きなだけ行えるようになるので、単純なDFSとかで「辺を最初に通るときの色を指定された色にできるか」を判定することができるようになる(色があってるときだけ遷移を行うDFSをやって、最終的に全部の辺を塗れたならOK)。始点(=普通の順で見た場合の終点)の選び方は自由なので、全部の頂点を始点として試してこのようなDFSをすればよい。なお操作を逆順で見ているので赤青どちらの色から始めるかにも自由度がある。これも2通り両方試せばよい。O(N(N+M))で十分間に合う。
ただ一点例外があり、閉路内のすべての辺を正しく塗ることができるような奇数長の閉路が存在する場合、その他の辺をすべて任意の色で塗ることができるようになる。なぜならその閉路内を一周することで色を切り替えた状態で元の頂点に戻ってくることができるので、塗りたい辺を塗った後また閉路に戻ってきて好きな色に切り替える、という操作が無制限に行えるようになるからである。よってこのような閉路を発見した場合、答えは必ずYESになる。
感想
はい天才 公式解説が既にわかりやすくてこれを見て解説ACした 最近解いた旧ARC-Dの中ではかなり最近のAtCoderっぽさを感じる
上書きは逆順!上書きは逆順!上書きは逆順!上書きは逆順!上書きは逆順!上書きは逆順!上書きは逆順!上書きは逆順!上書きは逆順!上書きは逆順!上書きは逆順!上書きは逆順!
コード (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, core.stdc.string; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto G = new Tuple!(int, int)[][](N); foreach (_; 0..M) { auto t = readln.split; auto u = t[0].to!int - 1; auto v = t[1].to!int - 1; int c = t[2] == "r"; G[u] ~= tuple(v, c); G[v] ~= tuple(u, c); } bool odd_cycle; auto dist = new int[](N); auto painted = new bool[][](N, N); void dfs(int n, int c) { dist[n] = c; int nc = c ^ 1; foreach (e; G[n]) { int m = e[0]; if (e[1] != nc) { continue; } if (!painted[n][m]) { painted[n][m] = painted[m][n] = true; } if (dist[m] != -1) { if (dist[m] != nc) { odd_cycle = true; } } else { dfs(m, nc); } } } foreach (u; 0..N) { foreach (c; 0..2) { odd_cycle = false; dist[] = -1; foreach (i; 0..N) foreach (e; G[i]) painted[i][e[0]] = false; dfs(u, c); if (odd_cycle || N.iota.map!(u => G[u].map!(e => painted[u][e[0]]).all).all) { writeln("Yes"); return; } } } writeln("No"); }
AtCoder Regular Contest 020: D - お菓子の国の旅行
https://atcoder.jp/contests/arc020/tasks/arc020_4
問題概要
N個の町があり、隣り合う町同士は道で結ばれている。町iと町(i+1)を結ぶ距離はDiとして与えられる。いまN個の町からK個の町を選び順に移動していくことを考える。このとき訪れる町に重複があってはならず、町から町への移動は必ず最短距離で行わなければならない。ただし始点と終点はどのように選んでもよい。このルールを守って移動する町の列を決めるとき、移動距離の合計がMの倍数となるようなものは何通りあるか求めよ。
N <= 100
M <= 30
K <= 10
解法
あるひとつの道に着目してその道が移動に何回使われるかということを考える。もし今見ている道が町3と町4を繋ぐものだった場合、その道が使われるのは(3以下の町→4以上の町)の移動と(4以上の町→3以下の町)の移動の2パターンである。つまり移動する町の列が与えられたとき、列の中で隣り合う2つの町のうち片方が3以下で片方が4以上となっている部分の数を数えればその道が使われる回数を出すことが出来る。例えばK=5で(5, 9, 1, 4, 3)の順に移動するとき、9->1, 1->4, 4->3 の移動で道3をまたぐので、道3は3回使われるということがわかる。
これをすべてのありうる移動列ごとに計算していけば当然答えは出せるが、移動列は最大で100C10*10!とかのパターンがあるのでまったく間に合わない。そこでさっきの考察に立ち戻ると、町iと町(i+1)を結ぶのコスト計算で必要なのは移動列そのものではなく「移動列に含まれる町のそれぞれが道の左にあるか右にあるか」という情報だけであった。このことを使うと移動列は愚直に持つ必要がなく、「左か右か」の情報だけを持ったbit列に潰すことができる。例えば先程と同じくK=5で移動列が(5, 9, 1, 4, 3)のとき、道3から見たこの移動列は(0, 0, 1, 0, 1)になる(道3より左の町を1, 右の町を0としている)。この形にしてしまっても、道が使われるのは 0 -> 1 への移動が行われる場所と 1 -> 0 への移動が行われる箇所だけということが依然としてわかるので、コストの計算は問題なく行うことができる。
以上を踏まえると、以下のようなbitDPを行うことができる。
dp(i, mask, m): i番目までの道までを見ていて、現在の道から見た移動列がmask(ビット列)で表され、コストの合計が m (MOD M) であるような場合の数
このDPの状態数はO(N * 2K * M)である。iからi+1への遷移ではmaskはそのまま維持されるか、どこかに1がひとつ増えることになる。例えば(5, 9, 4, 1, 3)の移動列は
- 道1から見ると (0, 0, 0, 1, 0)
- 道2から見ると (0, 0, 0, 1, 0)
- 道3から見ると (0, 0, 0, 1, 1)
- 道4から見ると (0, 0, 1, 1, 1)
という感じになっている。つまりmaskに1が1個増えるのは「さっきまでの道にとっては右だった町が今回の道からは左になる」パターンである。道は右にずれていくことを考えると1が減ったりすることはありえないし、同じ町には2度訪れないという制約を考えると1がいきなり2個以上増えたりしないこともわかる。この遷移はたかだかO(K)なので、状態数と併せてもO(NKM * 2K)で十分間に合う計算量になる。
感想
公式解説では何をどうbit列にしてるのかよくわからなかったのでkmjpさんのブログを見ました。木の問題とかを思うとひとつの辺に注目するというテク自体はそんなに突拍子がないものとは感じなくなってきたのはまあ成長といえるんだろうか 結局解けてないんだけど
コード (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, core.stdc.string; immutable long MOD = 10^^9 + 7; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto K = s[2]; auto A = iota(N-1).map!(_ => readln.chomp.to!int).array ~ 0; auto cross = new int[](1<<K); foreach (mask; 0..1<<K) cross[mask] = iota(K-1).map!(i => (mask & (0b11 << i)).popcnt == 1).sum; auto dp = new long[][][](N+1, 1<<K, M); // dp(i, mask): i番目の道まで見た / 訪問する町を順に並べた数列を「道iより左にあるか否か」でbitに変換したbitmask / コスト合計の mod M dp[0][0][0] = 1; foreach (i; 0..N) { foreach (mask; 0..1<<K) { foreach (j; 0..M) { int cost = (j + cross[mask] * A[i]) % M; (dp[i+1][mask][cost] += dp[i][mask][j]) %= MOD; foreach (k; 0..K) { if (mask & (1<<k)) continue; int nmask = mask | (1<<k); int ncost = (j + cross[nmask] * A[i]) % M; (dp[i+1][nmask][ncost] += dp[i][mask][j]) %= MOD; } } } } dp[N][(1<<K)-1][0].writeln; }
AtCoder Regular Contest 004: D - 表現の自由 ( Freedom of expression )
https://atcoder.jp/contests/arc004/tasks/arc004_4
問題概要
整数N, Mが与えられる。NをM個の整数の積として表す方法が何通りあるか求めよ。構成要素が同じでも並び順が異なればそれぞれ1通りとして数えるものとする。
|N| <= 109
M <= 105
解法
掛け算の中に現れるのはNの約数だけなので、まずはこれを求めておく。その上で素朴な解答を考えると以下のようなDPが立つ。
dp(i, j): Nの約数をi回掛けていて、現在の積がjであるような場合の数
このDPでjとしてありうるのはNの約数だけである。なぜなら現在の積が一度Nの約数以外になってしまったら、それに何を掛けてももうNにはできないからである。よってNの約数の個数をKとかで表すことにすると、このDPはiの状態数がM, jの状態数がKであわせてO(MK)の状態数になる。遷移も愚直にNの約数全部で試すことにすると、DPの計算量は全体でO(MK2)になる。109までの数だと約数の個数は多くて1350個くらいになる(cf. 高度合成数)ので、これは全然間に合わない。
ここでMが大きい場合ほとんどの数は1か-1になるということに注目する。たとえば1の次に小さい数である2であっても、30回かそこら掛け続けると109を超えてしまう。すると残りの数は全部1か-1で埋めるしかなくなる。というわけで、まずは1と-1以外の数を使ってNを作る場合の数を求めてから、あとでそれらの残りの部分に1を埋めるやり方の総数を求める、という方法を使うことができる。
1と-1以外の数を使う場合の数を求めるパートは上述のDPをやればよい。ただし1と-1を掛けるような遷移は行わないことと、掛ける回数は最大でも30回程度でよくなったことに注意する。計算量はO(MK2)のMが30になったもので 30 * 13502 となり十分間に合う(負の約数を考慮すると4倍になるが、それでも108くらいなのでそれなりの速度の言語なら問題ないはず)。
あとは各dp(i, N), dp(i, -N)に対して、余った数のぶんだけ1か-1を詰め込んでいく方法が何通りあるかを数えればよい。どれだけ余っているかはiを見ればわかる。また符号を調整する必要があるが、n個の1に対して-1にする数を奇数個選ぶ場合の数の総和と偶数個選ぶ場合の数の総和はどちらも 2 ^ (n - 1) である(二項係数の足し算)。最後に並べ替え方であるが、n個の1とM-n個のそれ以外のもの(区別しない)を並べ替えるやりかたは MCn である。これらをdp(i, N)に掛けていけばよい。
感想
公式解説へのリンクがないのでこれが想定解法なのかわからない DPの遷移はもっとうまく枝刈りできそうではあるけど
コード (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; immutable long MOD = 10^^9 + 7; void main() { auto s = readln.split.map!(to!long); auto N = s[0]; auto M = s[1]; if (N == 1) { if (M == 1) { writeln(1); } else { writeln(powmod(2, M-1, MOD)); } return; } long[] F; for (long i = 1; i * i <= abs(N); ++i) { if (N % i == 0) { if (i * i == N) { F ~= i; F ~= -i; } else { F ~= i; F ~= N / i; F ~= -i; F ~= -(N / i); } } } F.sort!"abs(a) < abs(b)"; int K = F.length.to!int; int[long] D; foreach (i, f; F) D[f] = i.to!int; const mx = 33; auto dp = new long[][](mx, K); dp[0][D[1]] = 1; foreach (i; 0..mx-1) { foreach (j; 0..K) { if (dp[i][j] == 0) continue; foreach (k; 2..K) { long x = F[j] * F[k]; if (x !in D) continue; (dp[i+1][D[x]] += dp[i][j]) %= MOD; } } } long ans = 0; auto Comb = new Combination(10^^5+10); foreach (i; 0..min(mx, M+1)) { foreach (j; K-2..K) { if (dp[i][j] == 0) continue; if (i == M && F[j] == -N) continue; long n = M - i; // 1か-1でn個埋める if (n == 0) { ans += dp[i][j]; ans %= MOD; continue; } long tmp = dp[i][j] * powmod(2, n - 1, MOD) % MOD; tmp = tmp * Comb.comb(M, n) % MOD; (ans += tmp) %= MOD; } } ans.writeln; } class Combination { long[] modinv; long[] f_mod; long[] f_modinv; this(int size) { modinv = new long[](size); modinv[0] = modinv[1] = 1; foreach(i; 2..size) { modinv[i] = modinv[MOD.to!int % i] * (MOD - MOD / i) % MOD; } f_mod = new long[](size); f_modinv = new long[](size); f_mod[0] = f_mod[1] = 1; f_modinv[0] = f_modinv[1] = 1; foreach(i; 2..size) { f_mod[i] = (i * f_mod[i-1]) % MOD; f_modinv[i] = (modinv[i] * f_modinv[i-1]) % MOD; } } long comb(long n, long k) { if (n < k) return 0; return f_mod[n] * f_modinv[n-k] % MOD * f_modinv[k] % MOD; } } 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; }
AtCoder Regular Contest 039: D - 旅行会社高橋君
https://atcoder.jp/contests/arc039/tasks/arc039_d
問題概要
N頂点M辺の無向グラフとQ個の旅行計画が与えられる。各旅行計画は始点、中継点、終点をあらわす頂点の組(A, B, C)からなる。各旅行計画について、一度も同じ辺を通ることなく始点→中継点→終点と移動することが可能かどうかを求めよ。同じ頂点は何度通っても良い。
N <= 105
M <= 2 * 105
Q <= 105
解法
グラフを二重辺連結成分分解し各成分をひとつの頂点と見なすと、これは各成分が元のグラフにおける橋によって繋がれた木になる(この辺の話は「二重辺連結成分分解」でググった方が早い)。
この木上で問題を考えると、木の各辺が必ず橋になっていることから、結局「始点Aが属する頂点 -> 中継点Bが属する頂点 -> 終点Cが属する頂点」の最短距離での移動が単純パスになっているか、という問題と同義である。この判定のためにLCAを使うことができる。自分は以下のような場合分けでやった。
- AがCの祖先であるとき <=> LCA(A, C) = A のとき このとき条件が成り立つのは「BがAとCの間にある」、つまり「AがBの祖先であり、BがCの祖先である」ときのみである。すなわち LCA(A, B) = A かつ LCA(B, C) = B が成り立っていればよい。
- CがAの祖先であるとき <=> LCA(A, C) = C のとき 1の逆をやればよい。
- 上記1, 2のどちらにも当てはまらないとき このときBはAかCどちらかの祖先でなくてはならず、またそうでない方とBのLCAはAとCのLCAと等しい。
まとめるとこの問題は 1. 二重辺連結成分分解をする 2. 分解後の各成分で木をつくる 3. 木に対してLCAとかをやってA->B->Cを通る単純パスが作れるかを判定する という3ステップで解くことが可能である。二重辺連結成分分解(とそれによる木の構築)の実装については例えば以下の Spaghetti Source のコードが参考になった。
(補足の追記)上の話だとA, B, Cが同じ連結成分に属している場合には必ず旅行可能である(つまり同じ二重辺連結成分内の任意の3点a, b, cに対して、a->b->cと移動するような単純パスが必ず存在する)と暗に仮定しているが、このことについての証明は公式解説に詳しい。(自分が解いたときはたぶんできるだろと思って決め打ちでやってしまったが、よく考えてみると全然自明な感じではなかった)
感想
二重辺連結成分分解のライブラリとLCAのライブラリをたまたま別件で作っていて、この問題で組み合わせて使ってみたらかなり便利だった コードの再利用ってすごいですね 対談形式のプログラミング入門の本に出てくる人みたいな感想ですいません
コード (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 s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto G = new UndirectedGraph(N); foreach (i; 0..M) { s = readln.split.map!(to!int); G.add_edge(s[0]-1, s[1]-1); } auto T = new BridgeBlockTree(G); auto L = new LCA(T.block.length.to!int, 0); foreach (i; 0..T.block.length.to!int) { foreach (j; T.adj[i]) { if (i < j) { L.add_edge(i, j); } } } bool check() { s = readln.split.map!(to!int); auto a = T.index[s[0] - 1]; auto b = T.index[s[1] - 1]; auto c = T.index[s[2] - 1]; auto ab = L.lca(a, b); auto bc = L.lca(b, c); auto ca = L.lca(c, a); if (ca == a) { return ab == a && bc == b; } else if (ca == c) { return bc == c && ab == b; } else { return (ab == ca && bc == b) || (bc == ca && ab == b); } } auto Q = readln.chomp.to!int; while (Q--) { writeln( check ? "OK" : "NG" ); } } class UndirectedGraph { int N; int[][] adj; this (int N) { this.N = N; adj = new int[][](N); } void add_edge(int u, int v) { adj[u] ~= v; adj[v] ~= u; } } class BridgeBlockTree : UndirectedGraph { // 二重辺連結成分分解 (橋で分解したあとの木) int[] index; int[][] block; Tuple!(int, int)[] bridges; this (UndirectedGraph g) { int n = 0; int cnt = 0; bridges = detect_bridges(g); auto is_bridge = new bool[int][](g.N); foreach (b; bridges) { is_bridge[b[0]][b[1]] = true; is_bridge[b[1]][b[0]] = true; } index = new int[](g.N); auto used = new bool[](g.N); void dfs(int n) { index[n] = block.length.to!int - 1; block.back ~= n; used[n] = true; foreach (m; g.adj[n]) { if (used[m] || m in is_bridge[n]) continue; dfs(m); } } foreach (u; 0..g.N) { if (used[u]) continue; block.length += 1; dfs(u); } super(block.length.to!int); foreach (u; 0..g.N) { foreach (v; g.adj[u]) { if (u < v && index[u] != index[v]) { adj[index[u]] ~= index[v]; adj[index[v]] ~= index[u]; } } } } Tuple!(int, int)[] detect_bridges(UndirectedGraph g) { Tuple!(int, int)[] bridges; int cnt = 0; auto ord = new int[](g.N); auto low = new int[](g.N); fill(ord, -1); fill(low, -1); void dfs(int n, int p) { ord[n] = low[n] = cnt++; foreach (m; g.adj[n]) { if (m == p) continue; if (ord[m] == -1) dfs(m, n); low[n] = min(low[n], low[m]); if (ord[n] < low[m]) bridges ~= tuple(n, m); } } dfs(0, -1); return bridges; } } class LCA { int n, root, lgn; int[][] g; int[] depth; int[][] dp; bool constructed = false; this(int n, int root) { this.n = n; this.root = root; lgn = bsr(n) + 3; g = new int[][](n); depth = new int[](n); dp = new int[][](n, lgn); } void add_edge(int u, int v) { g[u] ~= v; g[v] ~= u; } void construct() { auto stack = new Tuple!(int, int, int)[](n+10); int sp = 0; stack[0] = tuple(root, -1, 0); while (sp >= 0) { auto u = stack[sp][0]; auto p = stack[sp][1]; auto d = stack[sp][2]; sp -= 1; dp[u][0] = p; depth[u] = d; foreach (v; g[u]) if (v != p) stack[++sp] = tuple(v, u, d+1); } foreach (k; 0..lgn-1) foreach (i; 0..n) dp[i][k+1] = (dp[i][k] == -1) ? -1 : dp[dp[i][k]][k]; constructed = true; } void dfs(int u, int p, int d) { dp[u][0] = p; depth[u] = d; foreach (v; g[u]) if (v != p) dfs(v, u, d+1); } int lca(int a, int b) { if (!constructed) construct; if (depth[a] < depth[b]) swap(a, b); int diff = depth[a] - depth[b]; foreach_reverse (i; 0..lgn) if (diff & (1<<i)) a = dp[a][i]; if (a == b) return a; int K = lgn; while (dp[a][0] != dp[b][0]) { foreach_reverse (k; 0..lgn) { if (dp[a][k] != dp[b][k]) { a = dp[a][k]; b = dp[b][k]; K = k; } } } return dp[a][0]; } }
DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦: D - DISCO!
https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d
問題概要
どの文字もDISCOの5文字のうちいずれか1文字であるような文字列Sが与えられる。この文字列に対する以下のQ個の問に答えよ。
問: Sの区間[l, r]の範囲内で長さ5の部分文字列(連続でなくともよい)を抜き出したとき、それが"DISCO"となっているようなものは何通りか。mod 232 で答えよ。
|S| <= 106
Q <= 105
解法
自分がこの問題を解いたときは類題(ドワコン2018予選のC問題 k-DMC)を思い出しながら解いていた。この類題では、解法の1ステップとして以下のような小問題を解く必要があった(便宜上簡略化してます)。
問: いま見ている区間には 文字Aがa個, 文字Bがb個, 部分文字列ABがc個あることがわかっている。この区間を右にひとつだけ伸ばしたとき、この数はどのように変化するか?
答:
- 新たな文字が"A"であれば"A"の数が1増える
- 新たな文字が"B"であれば"B"の数が1増え、"AB"の数が"A"の数だけ増える
後者の「"AB"の数が"A"の数だけ増える」のところは「新たにBがひとつ後ろに付け加わったのであれば、前に出てきているAの分だけABが増える」という理屈である。
ではこれを少し変化させた以下のような問題だとどうなるか。
問: 区間[x, y)の文字Aの数, 文字Bの数, 部分文字列ABの数と、区間[y, z)の文字Aの数, 文字Bの数, 部分文字列ABの数がわかっている。この2つの区間をくっつけた区間[x, z)の文字Aの数, 文字Bの数, 部分文字列ABの数はどうなっているか?
答:
- [x, z)のAの数 = [x, y)のAの数 + [y, z)のAの数
- [x, z)のBの数 = [x, y)のBの数 + [y, z)のBの数
- [x, z)のABの数 = [x, y)のABの数 + [y, z)のABの数 + [x, y)のAの数 × [y, z)のBの数
足し算のところは元あったものをそのまま足しているだけなので問題ないと思う。また最後の掛け算も「後ろにBが付け加わると、前に出てきたAの分だけABが増える」という計算をしているだけなので、やっていることはさっきと同じである(というかそもそもさっきの問題はこの問題の特殊なパターンのひとつとみなすことができる)。
以上より、「左の区間と右の区間をあわせてひとつの区間にするとき、そこに含まれる部分文字列の数がどうなるか?」という問題に対する基本的なアイデアが得られた。上の例だと部分文字列が最大でも長さ2であるが、今回の問題のようにもう少し長いものが必要な場合でも同じことができる。たとえば左(s), 右(s)をそれぞれ左区間、右区間の部分文字列sの数であるとすると、両方をあわせた区間の部分文字列"DISC"の数は以下のように計算できる。
左("DISC") + 右("DISC") + 左("D") × 右("ISC") + 左("DI") × 右("SC") + 左("DIS") × 右("C")
このように左の区間の値と右の区間の値を合成することでより長い区間の結果を計算することができる。合成の際に変な演算をすることもないのでこれはセグメントツリーに乗せられそうだということがわかる。自分の実装では以下のような形のセグ木を作った。
- 各ノードは「Dの数, DIの数, DISの数, DISCの数, DISCOの数, Iの数, ISの数, ...」 のように"DISCO"のありえる連続部分文字列(15通り)についてそれぞれ何個あるかを配列とかで持っておく。
- 上の"DISC"の計算式の例のように左と右を合成したときどうなるかの計算式を15通りすべてに対して気合で書いてmerge関数を作り、セグ木の区間のマージをそれでやるようにする(コード参照)。
あとはこのセグ木に区間クエリを投げて、帰ってきた結果から"DISCO"の数にあたる部分を答えればよい。
実装上の細かい点として、この問題ではmodが232なので、C++であればいちいち剰余を取らずとも数をunsigned intで持っておくだけでよい(勝手にmod 232の値になる)。
感想
いきなりセグ木で殴る話をしてもあれなので自分の思考過程的な感じで書いてみたけど人が読んだらかなり意味不明な気がして不安になってきた それはともかくこの問題のおかげで結構良い順位取れたのでOKです
コード (C++)
※冒頭のコメントは「セグ木のノードに持たせるvectorにおいて、何番がどの部分文字列の数に対応しているか」をメモったもの(ひどい)
#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; typedef unsigned int uint; typedef vector<int> VI; typedef vector<ll> VL; /* 00: D 01: DI 02: DIS 03: DISC 04: DISCO 05: I 06: IS 07: ISC 08: ISCO 09: S 10: SC 11: SCO 12: C 13: CO 14: O */ const int K = 15; vector<uint> merge(vector<uint> a, vector<uint> b) { vector<uint> ret = vector<uint>(K, 0); REP(i, K) ret[i] = a[i] + b[i]; ret[1] += a[0] * b[5]; ret[2] += a[0] * b[6] + a[1] * b[9]; ret[3] += a[0] * b[7] + a[1] * b[10] + a[2] * b[12]; ret[4] += a[0] * b[8] + a[1] * b[11] + a[2] * b[13] + a[3] * b[14]; ret[6] += a[5] * b[9]; ret[7] += a[5] * b[10] + a[6] * b[12]; ret[8] += a[5] * b[11] + a[6] * b[13] + a[7] * b[14]; ret[10] += a[9] * b[12]; ret[11] += a[9] * b[13] + a[10] * b[14]; ret[13] += a[12] * b[14]; return ret; } class SegmentTree { public: vector<vector<uint>> table; int size; int offset; SegmentTree(int n) { size = 1; while (size <= n) size <<= 1; size <<= 1; table = vector<vector<uint>>(size, vector<uint>(K, 0)); offset = size / 2; } void assign(int pos, vector<uint> val) { pos += offset; table[pos] = val; while (pos > 1) { pos /= 2; table[pos] = merge(table[pos*2], table[pos*2+1]); } } vector<uint> query(int l, int r) { return query(l, r, 1, 0, offset-1); } vector<uint> query(int l, int r, int i, int a, int b) { if (b < l || r < a) { return vector<uint>(K, 0); } else if (l <= a && b <= r) { return table[i]; } else { return merge(query(l, r, i*2, a, (a+b)/2), query(l, r, i*2+1, (a+b)/2+1, b)); } } }; string S; int N, Q; int L[1010101]; int R[1010101]; void solve() { cin >> S >> Q; N = (int)S.size(); SegmentTree st = SegmentTree(N); REP(i, N) { vector<uint> v = vector<uint>(K, 0); if (S[i] == 'D') v[0] = 1; else if (S[i] == 'I') v[5] = 1; else if (S[i] == 'S') v[9] = 1; else if (S[i] == 'C') v[12] = 1; else v[14] = 1; st.assign(i, v); } while (Q--) { int l, r; cin >> l >> r; --l, --r; vector<uint> v = st.query(l, r); cout << v[4] << "\n"; } } int main() { cin.tie(0); ios::sync_with_stdio(false); solve(); }