AGC031-B

README

解法

1年ぶりに解き直してみたら、結構簡単に感じた。 We Love ABCのほうが難しいと思う。

dp[i]: i 文字目までのあり得る数列のパターンの通り数

この状態が建てられれば、遷移は結構自然。 反転は直近のものしか考慮する必要がなく、反転しない場合は直前の通り数を引き継ぐだけでよい。

唯一注意すべきは、今見ている数値と同じものの直近の登場位置が、1つ手前の場合は反転が考慮できないこと。 これは同じ数値が隣接している場合であり、反転操作を行っても出来上がる数列は同じであるため。

DPの特徴

• m 個手前の状態を参照することがある（「飛び石パターン」とでも名付けておく）