AtCoder Grand Contest 030 B問題メモ

B - Tree Burning

問題

1周 $L$ [m]の円形の湖岸に、等間隔で反時計回りに $0,1,2,...,L-1$ と座標が振られている
高橋君の家は座標0にある
$N$ 本の木が座標 $X_1,X_2,...,X_N$ の位置に立っている
- $1 \le X_1 \lt X_2 \lt ... \lt X_N \le L-1$
高橋君は自分の家から出発して、湖の円周上を以下のように移動して全ての木を燃やす
- 移動方向を決める
- まだ燃やしていない木にぶつかるまでは同じ方向に歩き続ける
- 燃やしていない木にぶつかると、その木は必ず燃やし、再度移動方向を決める、以下繰り返し
湖岸上の全ての木を燃やし尽くすまでの、最長距離を求めよ
$1 \le L \le 10^9$
$1 \le N \le 2 \times 10^5$

解法

こんなん、木に着くたびに常に折り返したらええんちゃうん、と思ったが、サンプル2で合わない。確かに、長い円周上の、家の近くにだけ木が左右同数生えているような状況では、常に折り返す方針ではその長い円周を活かさず終わってしまう。

円形問題は切り開いて数直線で考える。

0                        L=0
|------!----!-!!----!----|

移動の法則上、まだ燃やしていない木を飛び越えて奥の木を燃やすことは出来ないため、木の立つ位置は常に連続していて、燃やせるのは左右両端のいずれかの木のみとなる。

まず、これでDPを行うことを思いつく。

$DP[l][r][i]=l～r$ 番目の木が燃やされず残っている状況で、最後に燃やした木が $[i=0:左端/1:右端]$ だった時の最長移動距離

$l$ を $1～N$、$r$ を $l～N$ まで回さねばならず、$O(N^2)$ となる。これで部分点は取れる。

完全解答を得るには、$O(N)$ くらいの計算量に落とし込む必要がある。

左移動と右移動で燃やす本数を、固定して考えてみる。固定のパターン数は $N+1$ 通りある。

円周を、左移動と右移動に分けて割り開く。ワープが無くなるため多少考えやすい。この上を、ジグザグに移動していく。

サンプル2
X            6     3 2 1 0 9   7
家からの距離 6     3 2 1 0 1   3
             !-----!-!-!-o-!---!
                     <--- 
                     ------>
                   <--------
                   ------------>
             <------------------

0からジグザグに動くのを、「0からある木まで行って帰ってくる」を繰り返している、と考えると、距離は「家から各木までの距離」の2倍の和となる。

しかし、最後に燃やす木だけは帰る必要が無いので、1倍となる。

また、左右で折り返し回数の辻褄を合わせる必要があるため、場合によっては敢えて通過（燃やした後も同じ方向に動き続ける）した方がよい木もある。そのような木は距離が加算されない（0倍）となる。

つまり、各木の家からの距離に、以下の条件を満たすように、係数0,1,2を割り振って最大化すればよい。

'1'は1つだけ、左端か右端のいずれかに必ず必要
左右の'2'の数は、等しい、または'1'のある方が1つだけ少ない

X            6     3 2 1 0 9   7
家からの距離 6     3 2 1 0 1   3
             !-----!-!-!-o-!---!
係数         1     2 2 0   2   2
                     <--- 
                     ------>
                   <--------
                   ------------>
             <------------------

そう考えると、「左右の本数」「左右どちらに'1'を置くか」が決まった状態での最適な移動方法（係数の割り当て方法）は一意に決定する。

'2'は、左右いずれか少ない方まで、最大限使った方がよい
'0'を使わないといけない場合は、なるべく距離の小さい方に割り当てた方がよい

これは、公式解説pdfの「左右どちらかに進み、一度折り返した後は、常に折り返し続ける」行動と一致する。

'2'が割り当てられる区間は連続しているため、時計回り・反時計回りのそれぞれで家からの距離の累積和を取っておくことで、距離計算は $O(1)$ で行える。

左右の個数の決め方で $N+1$ 通り、左右どちらに'1'を置くかで2通り。全体で $O(N)$ で求まる。

import sys
from itertools import accumulate

circumference, n = map(int, input().split())
lll = list(map(int, sys.stdin.readlines()))
rrr = [circumference - l for l in lll]
rrr.reverse()
lll = [0] + lll
rrr = [0] + rrr
acc_l = [l * 2 for l in accumulate(lll)]
acc_r = [r * 2 for r in accumulate(rrr)]

# 左に0個右にN個（またはその逆）の場合は上手く計算できないので別に求めておく
ans = max(lll[-1], rrr[-1])

for take_l in range(1, n):
    take_r = n - take_l

    # 左に1が来る
    tmp_l = lll[take_l] + acc_l[take_l - 1] + acc_r[take_r]
    # 右に1が来る
    tmp_r = rrr[take_r] + acc_r[take_r - 1] + acc_l[take_l]

    # 0を使わざるを得ない分を引く
    if take_l < take_r:
        tmp_l -= acc_r[take_r - take_l]
        tmp_r -= acc_r[take_r - 1 - take_l]
    elif take_l > take_r:
        tmp_l -= acc_l[take_l - 1 - take_r]
        tmp_r -= acc_l[take_l - take_r]

    ans = max(ans, tmp_l, tmp_r)
print(ans)

目次

AtCoder Grand Contest 030 B問題メモ

B - Tree Burning

問題

解法