公式

D - Everyone is a winner 解説 by evima


First, for each \(1 \leq i \leq N\), let \(T_i\) be the time that elapses before someone solves \(i\) problems for the first time, assuming that each participant solves the problems in descending order of time required. Then, each participant \(i\) has to solve the first \(i\) problems within \(T_i\) minutes.

We can determine whether the condition can be satisfied by deciding the order each participant solves the problems, as follows.

  • For each \(i=N,N-1,\ldots,1\), in this order, do the following:
    • If it is impossible to solve the first \(i\) problems within \(T_i\) minutes, declare that it is impossible to satisfy the condition and terminate.
    • Otherwise, decide the first \(i\) problems so that the time needed to solve them is as long as possible while not exceeding \(T_i\) minutes. If there are multiple such choices, include as many problems requiring \(1\) minute as possible in the first \(i\) problems.
    • Then, solve the first \(i\) problems in descending order of time required. Afterward, solve the other \(N-i\) problems in descending order of time required, too.
    • Lastly, for each \(1 \leq j < i\), update \(T_j \mapsto \min\{T_j, t_{i,j}\}\), where \(t_{i,j}\) is the time taken for Participant \(i\) to solve the first \(j\) problems.
  • If we successfully decide the order every participant solves the problems, declare that it is possible to satisfy the condition and terminate.

In this algorithm, we did not check if \(t_{i,j} \geq T_j\) for \(i<j \leq N\). However, this inequality always holds when it takes \(1\), \(2\), or \(3\) minutes to solve a problem. This is because, for each \(2 \leq i \leq N\), if we have \(T_{i-1}+2 \geq T_i\) when we have done the operation for \(i\), we always have \(T_j \leq T_i+2(j-i)\) ( \(j \geq i\) ) at that moment. (For a more general setting, our greedy strategy does not work.)

The algorithm takes \(O(N^2)\) time if we naively update \(T\), but we can express \(T\) as a convex polyline consisting of line segments with slopes \(1\), \(2\), and \(3\) (after removing unnecessary parts) to make it work in linear time.

投稿日時:
最終更新: