ARC094 D - Worst Case

本番解けず。 1ステップでも考察入ると解けなくなるのは克服したい。

解法

自分より上位にn人存在しうるか、を二分探索して解いた。この問題は

  • n人の人が上位にいるとき、自分の順位を除いて、1回目に1位だった人は2回目n位、1回目2位だった人は2回目n-1位…という順位をとるのが最善

という単純な事実に気づけば後は二分探索で簡単に答えが求まる。 n人全員調べるとTLEなので、順位の積が最大になるのは真ん中あたりの人なので真ん中あたりの人だけ調べればいい。

Submission #2787487 - AtCoder Regular Contest 094