最適なプレイ方法を絞る

次が成り立つようなプレイ方法だけを考えても答えは変わりません。

\(2\) 回以上クリアするステージは高々 \(1\) つであり、存在するならばそれは \(1\) 回以上クリアするステージのうち最後のものである。

これは次のようにして示すことができます。

\(1\) 回以上クリアしたステージが \(1, \dots, M\) であるとする。\(i = 1, \dots, M\) のうち \(B_i\) が最小となるものの \(1\) つを \(m\) とおく。このとき、\(2\) 回以上クリアするのはステージ \(m\) だけであるとしてよい。これは、他のステージ \(i\) を \(2\) 回以上クリアする場合、\(B_i \geq B_m\) よりそれを \(m\) に置き換えても損しないことから従う。

さらに、\(m \lt M\) の場合、\(m \lt i \leq M\) となる \(i\) に対し \(A_i + B_i \gt B_i \geq B_m\) より、ステージ \(i\) の \(1\) 回目のクリアにかかる時間はステージ \(m\) の \(2\) 回目以降のクリアにかかる時間より長い。ステージ \(i\) は \(1\) 回しかクリアしないことを先ほど示したので、ステージ \(m + 1, \dots, M\) の \(1\) 回目のクリアを全てステージ \(m\) の \(2\) 回目以降のクリアに置き換えても損しない。

答えの計算

前節で最適なプレイ方法をかなり単純なものに限定することができました。よって、\(M\) の値を全探索し、「ステージ \(1, \dots, M\) を \(1\) 回ずつクリアし、残った回数は全てステージ \(M\) の \(2\) 回目以降のクリアに費やす」という方法を試して最小値を求めればよいです。

「ステージ \(1, \dots, M\) を \(1\) 回ずつクリアするための時間」を高速に求める必要があります。これは、\(M\) を \(1\) から順に試していくと、「現在の値に \(A_i + B_i\) を加える」という処理のみによって更新することができます。従って、この問題を \(O(N)\) で解くことができました。

なお、\(M \gt X\) となるような \(M\) は除外する必要があることに注意してください。

実装例 (C++)