問題概要
数直線上の $m $ 箇所に石の山 (pile) がある．$i$ 番目の山は位置 $X_i$ にあり，$A_i$ 個の石が積まれている．
以下の操作を任意の回数（$0$ 回でもよい）行うことができる：
- 石を一つ選ぶ．この石が位置 $x$ にあるとき，位置 $x + 1$ に移動させる．
正整数 $n$ が与えられる．閉区間 $[ 1, n ]$ 内のすべての整数点にちょうど $1$ つの石が置かれている状態にするために必要な操作回数の最小値を求めよ．不可能な場合はそのことを報告せよ．
制約
- $2 \leq n \leq 2 \times 10^9$
- $1 \leq m \leq 2 \times 10^5$
- $1 \leq X_i \leq n$
- $i \neq j \Rightarrow X_i \neq X_j$
- $1 \leq A_i \leq 2 \times 10^9$
解法
石を右にしか動かせないことから，より左にある格子点の方がそこに置く石の選び方の自由度が低いので，左から決めた方が良さそうに思えます．なので，山の情報は $X$ の値の昇順で与えられると仮定します．実際の入力はソート済みとは限りませんが，$O( m \log m )$ 時間のコストをかけることで，$X$ と $A$ を zip してソートするとか添字列を $X$ の値をキーにしてソートするなどの方法でソート済みにできます．
前提として，位置 $1$ に石を置くためには $1$ 以下の位置に山がある必要がありますが，制約も踏まえると $X_1 = 1$ でなければなりません．よって，このケースは先に条件判定して弾くことにし，以降 $X_1 = 1$ と仮定します．
位置 $X_1$ にある $A_1$ 個の石をどうするべきか考えます．$X_1$ 以上 $X_2$ 未満の整数点には位置 $X_1$ にあった石を置くしかありません．そのような整数点の数は $\Delta_X = X_2 - X_1$ 個あるので，$A_1 < \Delta_X$ の場合は石が足りないので不可能であることが分かります．以降，$\Delta_X \leq A_1$ と仮定します．$A_1$ 個の石の内 $\Delta_X$ 個を位置 $X_1, X_1 + 1, \dots, X_1 + \Delta_X - 1$ に配置することになりますが，その操作回数はそれぞれ $0, 1, \dots, \Delta_X - 1$ となります．よってその総和は $\frac { ( \Delta_X - 1 ) \Delta_X } 2$ です．$A_i - \Delta_X$ 個の石が余りますが，これらは $\Delta_X$ ずつの操作で位置 $X_2$ に移動させ，位置 $X_2$ の山に石が $A_2 + ( A_i - \Delta_X )$ 個あることにすれば，山の数が $m - 1$ 個の部分問題に帰着することができ，再帰的に問題を解くことができます．そのままやると最右の山を処理するときに特殊な判定をしなければなりませんが，位置 $n + 1$ に仮想的な山（番兵）があることにすれば，再帰ケースと同じ方法で判定ができます．番兵の位置までたどり着いたとき，そこに持ち越されてくる石の個数が $0$ 個ならば可能で，そうでなければ不可能です（途中で不可能と判定されていないことから不足はしていないので，（巷で言われているような）$\sum A = n$ と同値です）．
以上により，各山について $O( 1 )$ 回の四則演算で操作回数の計算と部分問題の構築ができるので，この部分は $\Theta( m )$ 時間で完了します．なので一番時間がかかるのは入力をソートする部分で，全体では $O( m \log m )$ 時間となります．
コード (C++)
int main() { IN( int, N, M ); VI X( M ), A( M ); cin >> X >> A; MAP_PRED( X ); X.PB( N ); VI indices( M + 1 ); iota( ALL( indices ), 0 ); sort( ALL( indices ), [&]( const int i, const int j ){ return X[i] < X[j]; } ); if ( X[ indices[0] ] ) { cout << -1 << endl; return 0; } LL res = 0, having = 0; REP( i, M ) { having += A[ indices[i] ]; const int dx = X[ indices[ i + 1 ] ] - X[ indices[i] ]; if ( having < dx ) { cout << -1 << endl; return 0; } res += LL( dx ) * ( dx - 1 ) / 2; having -= dx; res += having * dx; } cout << ( having ? -1 : res ) << endl; return 0; }
コード (Haskell)
main = do n <- head <$> readInts xs <- readInts as <- readInts let ( xs', as' ) = ( ( ++ [ n + 1 ] ) . map fst &&& map snd ) $ sort $ zip xs as dxs = zipWith (-) ( tail xs' ) xs' res = if head xs' /= 1 then Nothing else sum <$> sequence ( solve dxs as' 0 ) print $ fromMaybe ( -1 ) res solve [] _ 0 = [] solve [] _ _ = [ Nothing ] solve (dx:dxs) (a:as) h = res : solve dxs as ( h' - dx ) where h' = h + a h'' = h' - dx res = if h' < dx then Nothing else Just $ dx * ( dx - 1 ) `div` 2 + dx * h''
