AGC044 B - Joker (700)
最初の考察
愚直にやる場合を考える
それぞれの席からBFSで最短距離を求めるのが$ O(N^2)なので全体で$ O(N^4)
$ N \le 500なので間に合わない
最終的な考察
先にそれぞれの席からの必要なコストを求めていく
これは座席の位置からそれぞれ$ O(1)で求まる
離席する度にこのコストをBFSで減らしてゆく
空席の場合、その席より高いコストの所を自身と同じコストにする
空席で無い場合、その席のコスト+1より高いコストの所をその席のコスト+1にする
BFSするとその席のコストは最低でも1減るのでこの計算量は、初期の必要なコストの和の$ O(N^3)