[1] 必要条件について考える

人 \(i\) が復路で \(1\) 位となるための条件について考えてみましょう。

人 \(i\) よりも遅くスタートし、人 \(i\) よりも速くゴールしたような人 \(j\) (つまり、\(i < j\) かつ \(P_i > P_j\) であるような \(j\) ) が存在する場合、人 \(j\) は人 \(i\) より速く復路を走っているので、人 \(i\) は復路で \(1\) 位になり得ません。

したがって、「 \(i < j\) かつ \(P_i > P_j\) であるような \(j\) が存在しないこと」は人 \(i\) が復路で \(1\) 位となるための必要条件です。この条件を満たせば人 \(i\) は復路で \(1\) 位となることが可能でしょうか？

[2] 人 \(i\) に有利なレース結果を構成する

例えば、以下のレースは与えられた情報に合うレースです。

• 人 \(x\) は、復路を時刻 \(x\) にスタートし、時刻 \(N + P_x\) にゴールした。

ここから、スタートとゴールの順位を変えないまま、人 \(i\) にできるだけ有利なレース結果を作っていきましょう。

まず、人 \(i\) よりも遅くゴールした人のゴール時刻に \(10^{100}\) を加算します。

• 人 \(x\) は、復路を時刻 \(x\) にスタートし、時刻 \(N + P_x + [P_i < P_x] \times 10^{100}\) にゴールした。

順位を変えずに、「人 \(i\) よりも遅くゴールした人」の復路のタイムを人 \(i\) より遅くすることができました。

同様に、人 \(i\) よりも速くスタートした人のスタート時刻から \(10^{100}\) を減算すると、

• 人 \(x\) は、復路を時刻 \(x - [x < i] \times 10^{100}\) にスタートし、時刻 \(N + P_x + [P_i < P_x] \times 10^{100}\) にゴールした。

順位を変えずに、「人 \(i\) よりも速くスタートした人」の復路のタイムを人 \(i\) より遅くすることができます。

[3] まとめ

[2] から、人 \(i\) が [1] の必要条件を満たせば、人 \(i\) が復路のタイムで \(1\) 位になるようなレース結果を構成できることがわかります。したがって、各 \(i\) について、\(i < j\) かつ \(P_i > P_j\) であるような \(j\) が存在するかどうかを判定すればよく、\(O(N^2)\) 時間で解くことができます。

また、\(P\) の後ろからの累積 min を取ることで、\(O(N)\) 時間で解くことができます。