解法は TopCoder SRM614 解説 を参考にしてください。流れは、だいたい以下のとおり。 全てのループを断ち切るように N + M - 1 箇所のマスを変数化 斜めに変数化すれば max(N, M) 箇所でよい すべての箇所の期待値を、DP を使って (N + M - 1) 変数多項式で…

第一段階で、各々の長さの彩色パターンを DP で求めて、 第二段階で、第一段階で求めた彩色パターンを使って、同じような DP を構築する。K 色全てを状態にするのではなく、開始地点と同じ色かそうでないかの２通りだけの状態を考えれば良い。具体的な処理は…