ABC265 E - Warp (500)
ワープの機動は
$ 3^N
通りになり全てを確かめるのは不可能
$ dp[i][j][k]
で合計
$ i
回の移動で1種類目のを
$ i
回、2種類目のを
$ j
回、3種類目のを
$ k
回選んだ場合の数とする
ちょうどその場所が障害物がある場所ならそこには遷移できない
逆に無いならそこに遷移できる
遷移元はいずれかの移動をした回数が1少ない3箇所から
$ i+j+k=n
である全ての地点での値の和が答え
$ \mathcal{O}(N^3 \log M)
問題:
https://atcoder.jp/contests/abc265/tasks/abc265_e
提出:
https://atcoder.jp/contests/abc265/submissions/34231916
#ABC265
#500pt
#E
#ABC
#AtCoder