けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

あみだくじ

AtCoder ABC 113 D - Number of Amidakuji (400 点)

あみだくじ 問題へのリンク 問題概要 縦棒の個数が 、横棒が縦方向に 刻みのあみだくじであって、 番目からスタートすると 番目に到着するようなものを数え上げよ。 制約 考えたこと いかにも DP という感じではあるね。 dp[ i ][ j ] := 縦棒を上から i 刻…