AGC048 C - Penguin Skating (700)
0番のマスとL+1番のマスにも動かないペンギンがいるものとする
i番目のペンギンが移動できる先は$ j個左のペンギンの現在地 + jか$ j個右のペンギンの現在地- jのマス目のみ
右に移動するのを>、左に移動するのを<、移動しないのを|で表すと、|<<<>>>>>>|<<>>|<<のように移動しない点に対して統一された方向になっている必要がある
移動先を求めるのに使う$ al[i] = a[i] + (n - i) とした配列を持っておく
$ (n - i)の部分で上の式の$ \pm jの所を消している
これを行わず、aから二分探索して目的の位置の左右の点を見る実装にすると、その更に先に目的地があった場合にWA
左右の移動方向毎に以下をやる
同じ矢印の終点方向から計算していく
$ b[j]+(n-j) と同じ値がalにあるかを確かめる
無い場合は移動不可能なので-1
移動する場合はその目的の点と今の点の間の点を最初に動かす必要があるので、その分だけ移動回数を増やす
ただし、$ b[j] が一つ前と1しか違わない場合、前回の移動で移動完了しているためカウントはしない
これを移動しない点に到着するまで繰り返す
移動先の二分探索を毎回やるのがボトルネックで$ O(N \log N)