AGC-030:Tree Burning - 思考の墓場

解けてよかった。

問題:

考察

まず，高橋君はどういう動きをすべきかを考えよう。直感的に， $0(L)$ を中心として，左右に振れるような動きをしたくなる。つまり

最初は $i$ 本分右に進んで，それ以降は左→右→...と進む。(1)
最初は $i$ 本分左に進んで，それ以降は右→左→...と進む。(2)

これを $i=1...N$ で試したとき，その最大値が答えになる(この部分が非自明ですね，わかり次第(そして余裕ができ次第)追記します)。部分点解法は， $i$ を固定したあと，この動きを愚直にシミュレーションすればよい。
Submission #3894463 - AtCoder Grand Contest 030

では，満点解法を考えよう。要は，部分点解法ではシミュレーションに $O(N)$ かけて答えを求めているが，これが $O(1)$ でできれば満点だ。これはすぐにはわからないので，実験をしてみよう。例えば $N=5$ で， $i=1$ としてみよう。このとき，高橋君の歩いた距離は(実際に手を動かしてください)
$x_1 + \{x_1 + (L-x_5)\} + \{(L-x_5) + x_2\} + \{(x_2 + (L-x_4)\} + \{(L-x_4) + x_3\}\\\ =2x_1 + 2x_2 + x_3 - 2x_4 -2x_5 + 4L$
さて，これを見てなんだかきれいそうな形をしているなあと思えないだろうか。実は，一般的には以下のような結果になる。対称性のため，(1)のパターンだけ述べることにする。