SRM647 div1 250

問題

1〜Nの番号が付けられた建物を直線状に順番に並べて建てたい。
ただし、以下の条件が与えられる。
・1の建物の高さは0
・隣り合う建物の高さの差は高々1となるようにしたい。
・x[i]の建物の高さがt[i]以下
このとき、建物の高さの最大値を求める。

N<10^5
x.size()<=min(N,50)
t[i]<=10^5

考え方

計算で求めると大変なので、シミュレーションする。

本番では、1,x[i],Nの建物の高さを、他の建物を+1し続けてた場合より高い場合、その高さまで低くしておいて、この建物間の高さをシミュレーションして求めた。
今、建物aと建物bの間をシミュレーションしようとすると、
・aの高さを+1しつづけてbの建物の場所でbの高さと一致するなら最大はbの高さ
・bの高さを+1しつづけてaの建物の場所でaの高さと一致するなら最大はaの高さ
・上記以外なら、aの建物とbの建物の両方向から低い高さの方だけ+1して埋めて、同じ高さなら一緒に+1を更新、全部埋めてたら終了
ということを繰り返す。

上のは無駄なことをいろいろやってしまっていて、以下のように行きと帰りの2回なめればよい。
N個の配列hを用意しておいて、h[1]=0、h[x[i]]=t[i]、h[otherwise]=∞としておく。
1->N方向に、次の建物が∞なら現在の建物の高さ+1を次の建物の高さにしておく。これで片方の満たすべき条件を満たした状態ができる。
次に、N->1方向に、同様に次の建物の高さが現在の建物の高さ+1より大きければ、建物の高さ+1に置き換える。
これで両方向から差が1以下を満たして最適な状態を求められる。