xxxasdfghjk999のブログ

iroiro

ABC 041-D 徒競走

問題

解法

$N \leq 8$ のときの部分点はnext_permutationを使うと獲得できます.
満点解法では $16! = 2.0 * 10^{13}$ 通りを考える必要があるので, 別の解法を考える必要があります.
$2^{16} = 65536$ と, うさぎの集合を見るようにすると数が小さいです.
これに着目して, bitDPを行うことを考えます.
$dp[S][n] = 集合Sにおいてn番目のうさぎが最後尾であるときの並べ方$
とすると,

基底

$dp[\{n\}][n] = 1$

遷移

$dp[S][n] = 0 \space (\exists_k ( (n < k) \land k \in S)$ )
$dp[S][n] = \sum_{(k \in (S-\{n\})) } dp[S-\{n\}][k] \space (otherwise)$
とかけます. 遷移においての $(n < k)$ というのは, 与えられた $\{x\} , \{y\}$ について, 最後尾が $n$ であるが, $k \in S$ より $n$ の方が速いといったときには矛盾を孕むことになるので, そのような場合の数は存在せず $0$ となる, ということです.

提出

Submission #3221481 - AtCoder Beginner Contest 041

感想

$M$ についての制約をよく見ておらずに領域を十分にとっておらず, ACときどきWA状態でｵﾝｵﾝしてました. 領域足りてなかったらREでてほしいです...(我儘).