Colorful Blocks - abc 167 e
#数え上げ
まず, 超素朴な dp を書いてみる O(N^3)
https://atcoder.jp/contests/abc167/submissions/13093316
遷移をまとめられそう O(N^2)
https://atcoder.jp/contests/abc167/submissions/13094970
dp[i][j] : i 番目のブロックを見ていて, これまでの隣り合う同じ色の ブロックの数の和が j
もう 1 段くらい書いたら見えてくる
場合の数の経路の問題に似ている
ソースコード
https://atcoder.jp/contests/abc167/submissions/13096583
別解
参考 : 公式 youtube editorial
隣り合うブロックで同じ色の数は決め打ち (探索) する
x とする
隣り合うブロックが同じ色なら連続部分を囲ってる
3 つ以上連続する場合書いてない...
K = 0 なら,
M * (M - 1) * (M - 1) * ...
= M * (M - 1)^(N - 1)
最初以外はその手前の色以外
今回, 囲った部分単位で見る
囲みの個数は N - x
最初囲みの個数は N で, 隣と同じ色になるごとに 1 減る
よって, M * (M - 1)^(N - x - 1)
あとは, 隣り合うブロックで同じ色の数は決め打ちしたが, どこにするか決めてない
ブロック間 N - 1 箇所から x 箇所選ぶ
