AtCoder Grand Contest 030：B - Tree Burning

問題

https://atcoder.jp/contests/agc030/tasks/agc030_b

制約

  • 2 \le L \le 10^9
  • 1 \le N \le 2 \times 10^5

考え方

円周上の最長距離を求めるわけだが、以下のように円を切り開いて直線上で考えるほうが見通しがよくなる(気がする)。

f:id:d_tutuz:20181231102316p:plain
円を切り開いて直線にするイメージ図

距離が長くなるように進むわけだが、まずぱっと思いつくのはスタート地点からジグザグに進む方針である。しかしサンプルから分かるようにこの方針では最長距離にならないことがある。実は最長距離の候補はまず　i だけ右または左にそのまま進んで、その後はジグザグに進むということで求めることができる。

部分点解は、この「i だけ右または左にそのまま進んで、その後はジグザグに進む」という考察をそのまま実装すればよい。右からの最長距離を求められたら、左からは元の数列を逆にするのが実装が楽になって良い気がする。

Submission #3903016 - AtCoder Grand Contest 030

満点解は calc() のシミュレーションに O(N) かかっているところを O(1) にすることが必要である。これも実は以下のようなシンプルな式であらわすことができる。詳しくはを参考1を参照されたい。具体的な計算から式を割り出して、一般的な式を推測するようなことが必要と考えている。\{s_N\} は \{x_N\} の累積和とする。

(i): (i + N) が偶数の時

2 * (s \lbrack m-1 \rbrack - s \lbrack i-1 \rbrack ) + x \lbrack m \rbrack - 2 * (s \lbrack n \rbrack - s \lbrack m \rbrack ) + (N-i) * L

(ii): (i + N) が奇数の時

2 * (s \lbrack m-1 \rbrack - s \lbrack i-1 \rbrack ) - x \lbrack m \rbrack - 2 * (s \lbrack n \rbrack - s \lbrack m \rbrack ) + (N-i) * L

これが分かると、 calc() のシミュレーションが O(1) で求めることができるので、全体の計算量は (N) となり間に合う。

Submission #3902964 - AtCoder Grand Contest 030

どこに着目して考察するべきだったか

円は直線に切り開いて求めて考えてみると、見通しがよくなることがありそう。「まず i だけ進んでその後ジグザグで最適」という点に気づけるかどうかがポイントだったように思える。

何がバグっていたか

  • サンプルが合わない実装はしない。

得た知見

  • 円は直線にしてみる
  • 具体的な計算から一般解を推測する
  • 逆向き計算は、元の数列を逆にすると実装が楽になることがある

部分点別解(DP)

DPで解くことができる。

dp \lbrack i \rbrack \lbrack j \rbrack \lbrack 2 \rbrack := 左から i 番目、右から j 番目で今いる状態が k \ (k=0( 左にいる状態 ), k=1( 右にいる状態 ))

として、DPの遷移は

  • 右にいる状態から右に移動する
  • 右にいる状態から左に移動する
  • 左にいる状態から右に移動する
  • 右にいる状態から左に移動する

の 4 パターンである。これをそのまま実装すると O(N^2) かかるので部分点を得ることができる。

Submission #3903328 - AtCoder Grand Contest 030

DPで解けるかもしれないという気持ちになれば、DP解のほうが部分点としては自然な気がする。

類題

参考

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