問題

  • すべての階で、ちょうど1人だけが降りるor乗る
  • 1階で乗った人が降りる階をkとすると、2,3,..,k-1階では人が乗り、彼らはk+1,..,2k-2階で降りる
    • したがって、上のようなペアから成る区間に分割できるかどうかが問題
  • 方針：0<=i<j<2Nについて、[i,j]が上のような条件を満たすかどうかを全部チェック
    • 区間の数n^2。一つの区間でのチェックのコストnより、O(n^3)