ABC113 D Number of Amidakuji

言い訳

codevsたのしかったです

例の表

https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0

所見

一発で思いついたぞヤッホーと思っていたら既に解いた問題だった(は？)

問題概要

https://atcoder.jp/contests/abc113/submissions/5408429
特定条件をみたす「正しいあみだくじ」のうち、左から1番目の線から始めた時左からK番目の線に到達するものの個数を1000000007で割った余りを求めよ。

取った方針

直線がW <= 8本しかないので、1行について全探索ができる。
y行目のx列目(0 origin)にいる場合の数をdp[y][x] とおくと、x-1番目の間(0 origin) に直線があるときdp[y+1][x-1] += dp[y][x]、x番目の間に直線があるときdp[y+1][x+1] += dp[y][x]、両方に直線がない時dp[y+1][x] += dp[y][x] のようなDPができる。
dp[H][K] が答え。

正しい方針

同上

得られた知見

• m次元->1次元 x mにしてO(N^m)をO(Nm)にするテク(頻出っぽい)
  • 独立に考えてもいいものは独立に考える
• 場合の数 -> 纏められる状態(今回はy行x列に到達するあみだくじの数)を纏めて考える

解くのに必要な要素

• 独立に考えてもいいものを独立に考える -> DP

周辺調査によって得られた知見

特になし