Closed5ヶ月前にクローズ5

EDPC Y Grid2

競技プログラミング

動的計画法

EDPC Y Grid2 考察ノート

考察

よくある、グリッドを右下に向かって移動する経路を数える問題。
ただし、グリッドサイズが巨大で、壁の配置は疎ら。つまり、座標圧縮が必要。
圧縮した場合の数え上げ法をよく考える必要がある。

座標圧縮すると行・列の情報が失われてしまい、正しく計算できない。
全体 ${H+W \choose H}$ から、壁を通るルートを引くのも無理そう。通る壁の種類と包除原理を組み合わせると計算量が $O(N!)$ になる。

壁の数だけで何とかできる？
$n+1$ 個の壁を通るには $n$ 個の壁を通る必要がある。
$n$ 個以上の壁を通過する場合で包除原理。 $dp[0] - dp[1] + dp[2] - dp[3] + \cdots$ 。
壁の座標を遷移順にソートすればDPで $O(N^2)$ で計算できる！

回答

投稿時点で最速
包除原理の実装に注意が必要。通過する壁の個数ではなく、通過した壁の番号（ソート後）でDPする。

その他

$\frac{1}{n!} = \frac{n+1}{(n+1)!}$ を利用すると、階乗の逆数の一覧を $O(N\log \mathrm{MOD})$ でなく $O(N + \log \mathrm{MOD})$ で得られる。

このスクラップは5ヶ月前にクローズされました