CODE FESTIVAL 2016 Final: F - Road of the King

https://atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_f

問題概要

N個の町があり、これらの間にはひとつも道が存在しない。はじめ王様は町1におり、今いる町からN個の町のどれかへ移動することをM回繰り返す(移動元と移動先は同じでもいい)。各移動のたびに、移動元の町aから移動先の町bに一方通行の道が作られる。M回の移動の終了後に道だけを使って任意の2つの町が行き来できるようになっているという条件を満たすような移動の仕方が何通りあるか求めよ。

解法

移動の性質を考えると以下のことが言える。

  • 性質1. 先に訪れた町は後に訪れるすべての町に必ず到達可能
  • 性質2. 既出の町xへの後戻りが発生したとき、これまでに訪れているすべての町からxへ到達可能になる

性質1は移動によって有向辺が張られていく様子を想像するとわかりやすいと思う。性質2は性質1から導くことができる。さらにこれらを用いて以下のことが言える。

  • 性質3. スタート地点である町1への後戻りが発生したとき、これまでに訪れているすべての町は相互に到達可能になる
  • 性質4. 性質3によって相互に到達可能になった町のいずれかへの後戻りが発生したときも、同様にこれまでに訪れているすべての町は相互に到達可能になる
  • 性質5. 上記の性質3, 4以外ですべての町が相互に到達可能になるようなことはない。

これは性質1より常に「町1->これまでに訪れているすべての町」が到達可能であることからわかる。ここまでを踏まえると以下のようなDPが立つ。

dp(i, S, T): i回の移動を行って、町集合Sに訪問済であり、町集合T内の町はすべて相互に到達可能になっているような移動の仕方の総数

求めたいのはdp(M, 全部の町, 全部の町)である。町集合の部分がネックになるが、実はこの問題では愚直に集合そのものを持つ必要はない。スタート地点である町1以外のすべての町は対称なので、必ず番号順に町を訪れると仮定してしまってよい。答えに関しては最後に[2, 3, ..., N]の任意の置換の総数(N-1)!を掛ければ辻褄を合わせられる。というわけでDPは以下のように軽くできる。

dp(i, j, k): i回の移動を行って、町1〜jまで訪れており、町1〜kがすべて相互に到達可能になっているような移動の仕方の総数

遷移は「町(1〜k)のどこかに移動する(これによって町(1〜jが)すべて相互に到達可能になる)」「町(k+1〜j)のどこかに移動する」「新しい町(j+1)に移動する」のどれかである。これらはO(1)で計算できるのでDPの計算量はO(N2 M)となる。

感想

なんか考えてたらできた うれしい

コード (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 dp = new long[][][](2, N, N);
    dp[0][0][0] = 1;

    int cur = 0;
    int tar = 1;

    foreach (i; 0..M) {
        foreach (j; 0..N) {
            foreach (k; 0..N) {
                dp[tar][j][k] = 0;
            }
        }
        foreach (j; 0..N) {
            foreach (k; 0..N) {
                if (dp[cur][j][k] == 0) {
                    continue;
                }
                if (j < N - 1) {
                    (dp[tar][j+1][k] += dp[cur][j][k]) %= MOD;
                }
                (dp[tar][j][k] += dp[cur][j][k] * (j - k) % MOD) %= MOD;
                (dp[tar][j][j] += dp[cur][j][k] * (k + 1) % MOD) %= MOD;
            }
        }
        swap(cur, tar);
    }

    long ans = dp[cur][N-1][N-1];
    foreach (i; 1..N) ans = ans * i % MOD;
    ans.writeln;
}