SoundHound Programming Contest 2018 Masters Tournament 本戦: C - Not Too Close
問題概要
N頂点の無向グラフで、頂点に1からNまでの番号がついており、自己辺・多重辺を持たず、すべての辺の長さを1としたとき頂点1-2間の最短距離がDであるようなものが何通りあるか求めよ。
D < N <= 30
解法
頂点1を基準として、「頂点1から距離1の頂点」「距離2の頂点」...という風にどんどん頂点をくっつけてグラフを構成していくことを考える。この数え上げは以下のDPで行える。
dp(i, j, k): 距離iまで構成し、j個の頂点を使い、最後にくっつけた距離iの頂点の数がk個であるグラフの数
距離dの頂点を追加するときは、以下のことを考慮に入れる。
- 何個の頂点を距離dとしてくっつけるか
- 頂点の選び方は何通りあるか
- 辺の張り方は何通りあるか
頂点の選び方は(未使用頂点の数)から(使用頂点の数)を選ぶ組合せなのでコンビネーションで計算できる。ただし頂点2の扱いに注意が必要で、距離がDではないときに頂点2を選んではいけないし、候補にも入れてはいけない。逆に距離がDの時は頂点2は必ず選ぶ。この点で上の組合せの計算には微妙に足し引きが入る。
辺の張り方に関しては以下のことを考慮に入れる → 距離(d-1)の頂点のうち少なくともひとつには辺を張らなければならない。距離(d-2)以下の頂点には辺を張ってはならない。また距離dの頂点同士は好きなだけ辺を張れる。
最後に作ったグラフのうち余った頂点がある場合、その余った頂点同士でいくらでも辺が張れるという点に留意する。
状態数がO(N3), 遷移がO(N)(何個頂点をくっつけるかの列挙)なのでO(N4). Nが小さいのでこれで十分間に合う。
感想
解説聞いたうえで実装し始めたけど最後の余った頂点のところを見落としててドツボに入ってしまった。考え方自体は確かにどこかで見たことあるといえる感じなのでちゃんとできるようになっておきたい
コード (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; long[] F; long[] G; void main() { F = new long[](50); G = new long[](50); F[0] = F[1] = 1; foreach (i; 2..50) F[i] = F[i-1] * i % MOD; foreach (i; 0..50) G[i] = powmod(F[i], MOD-2, MOD); auto s = readln.split.map!(to!int); auto N = s[0]; auto D = s[1]; auto dp = new long[][][](N, N+1, N+1); dp[0][1][1] = 1; foreach (d; 1..N) { foreach (using; 1..N+1) { foreach (used; 1..N+1) { if (using + used > N) continue; foreach (last; 1..N+1) { long rest = d <= D ? N - used - 1 : N - used; long k = d == D ? using - 1 : using; if (rest < k) continue; long tmp = comb(rest, k); tmp = tmp * powmod(powmod(2, last, MOD) - 1, using, MOD) % MOD; tmp = tmp * powmod(2, using * (using - 1) / 2, MOD) % MOD; (dp[d][using+used][using] += dp[d-1][used][last] * tmp % MOD) %= MOD; } } } } long ans = 0; foreach (d; D..N) foreach (n; d+1..N+1) foreach (last; 0..N+1) { long tmp = dp[d][n][last]; tmp = tmp * powmod(2, (N-n)*(N-n-1)/2, MOD) % MOD; ans = (ans + tmp) % MOD; } ans.writeln; } long powmod(long a, long x, long m) { a %= m; long ret = 1; while (x) { if (x % 2) ret = ret * a % m; a = a * a % m; x /= 2; } return ret; } long comb(long n, long k) { return F[n] * G[n-k] % MOD * G[k] % MOD; }