オンサイトで未確認

ukuku09の活動記録。

AtCoder Beginner Contest 042 D: いろはちゃんとマス目

引き続きABC埋め。

 

問題文

abc042.contest.atcoder.jp

解法

お絵描きするとわかる。

左上を $(0, 0)$、右下を $(H-1, W-1)$ とする。障害物がなければ、グリッド内を左上から右下へ、右移動・下移動のみで移動する経路数は、全移動(H-1+W-1 回)のなかのどこで右に移動(W-1 回)したかの選び方に等しく、$$\frac{(H-1+W-1)!}{(W-1)!(H-1)!}$$ という組み合わせの数で求められる。

ただし、今回は下からAマス以内、左からからBマス以内には入れないので、$(0, 0)$ から $(H-A-1, i)$ と $(H-A, i)$ から $(H-1, W-1)$($B \leq i \leq W-1$)という経路に分解して数え上げる。