小課題

難易度で二分探索することにします。 難易度を決めると、それより難易度が大きいリズムアイコンはタップできず、そうでなければタップするかどうかを自由に選ぶことができます。 したがって、部分和問題に帰着でき、 \(O(XM \log K)\) などで解くことができます。 \(dp[m][x]\) を \(m\) 番目のリズムアイコンまで見てスコアを \(x\) にするのに必要な難易度の最大値の最小値 として更新すれば二分探索をする必要がなくなり、 \(O(XM)\) で解くこともできます。

満点

難易度で二分探索することにします。 難易度の制約から、連続してタップできないリズムアイコンの区間がいくつか存在します。 どのリズムアイコンをタップするかを前から決めていくとき、連続してタップしているリズムアイコンはできるだけ少ないほうがいいため、\(dp[m][x]\) を \(m\) 番目のリズムアイコンまで見てスコアを \(X\) にするときに直近で連続してタップしているリズムアイコンの最小値として計算していくことで、 \(O(XM \log K)\) で解くことができます。

おまけ

元々提案されていたのは難易度の総和を最小化する問題でしたが、結構複雑で、解法の区別もテストケース作成も大変だったのもあり、現在の形に改題しました。\(O(XM^2+K)\) または \(O((MX+XK)logM)\) が想定されていたので考えてみてください。もっといい解法があれば教えてください。