概要

この問題は、実は「スタート地点 \(0\) を含む、バリケードのない連続区間」だけを考えれば十分です。
その区間内で各移動プランを「使う / 使わない」の到達可能位置 DP を行い、これを bitset で高速化します。

考察

1. 重要なバリケードは、\(0\) の左右で一番近いものだけ

まず、座標 \(0\) にバリケードがある場合を考えます。

高橋君は最初に座標 \(0\) にいるので、どんな移動をしても移動区間は必ず \(0\) を含みます。
したがって \(0\) にバリケードがあると、すべての移動プランが衝突して実行不能です。
このとき答えは \(0\) です。

以降、\(0\) にバリケードがないとします。

• \(L\) := \(0\) より左にあるバリケードのうち、最も右のもの
• \(R\) := \(0\) より右にあるバリケードのうち、最も左のもの

を考えます（存在しない場合は \(\pm\infty\) とみなします）。

すると、\(0\) は区間 \((L, R)\) の中にあります。
しかも、この区間の内部にはバリケードが 1 本もありません。なぜなら、\(L, R\) は「\(0\) に最も近い左右のバリケード」だからです。

ここで、現在位置 \(s \in (L, R)\) から \(t\) へ移動するとき：

• \(t \in (L, R)\) なら、区間 \([s,t]\) 全体が \((L,R)\) に入るので、途中にバリケードはありません
• \(t \notin (L, R)\) なら、移動中に必ず \(L\) または \(R\) をまたぐので衝突します

つまり、移動が可能かどうかは「移動後の位置が \((L,R)\) に残るか」だけで決まるのです。

したがって、\(L\) より左のバリケードや \(R\) より右のバリケードは、そもそもそこまで到達できないので無視できます。

---

2. 座標の範囲はさらに絞れる

\(S = \sum_{i=1}^{N} |D_i|\) とします。

どのプランをどう選んでも、移動した距離の合計の絶対値は \(S\) を超えません。
したがって、高橋君が取りうる座標は必ず \([-S, S]\) の中にあります。

よって、考えるべき座標は

\([ [L+1, R-1] \cap [-S, S] ]\)

だけで十分です。
これを整数座標の範囲 \([lo, hi]\) として持てばよいです。

---

3. あとは「使う / 使わない」の DP

安全な整数座標の範囲が分かったので、各プランを順に見ながら

• スキップする
• 実行する（移動後も安全範囲内にいるときだけ）

という DP を行えばよいです。

たとえば、現在到達可能な位置が \(\{-3, 0, 2\}\) で、次の移動が \(+4\) なら、

• スキップしてそのまま \(\{-3,0,2\}\)
• 実行して \(\{1,4,6\}\)（範囲外は除く）

の和集合が次の到達可能位置になります。

---

4. 素朴 DP は重い

範囲の長さを \(W = hi - lo + 1\) とすると、\(W \le 2S+1 \le 100001\) です。

普通に - dp[i][x] = i 個目まで見たとき座標 x にいられるか

のような DP をすると、各プランごとに全座標を見るので \(O(NW)\) かかります。
最悪で \(5 \times 10^4 \times 10^5\) 程度となり、かなり重いです。

---

5. bitset で高速化できる

到達可能な座標集合を bitset で持つと高速になります。

• bit \(k\) が \(1\) ⇔ 座標 \(lo + k\) に到達可能

とします。
このとき、移動量 \(d\) を実行する操作は bitset のシフトで表せます。

• \(d > 0\) のとき: 左シフト << d
• \(d < 0\) のとき: 右シフト >> (-d)

さらに、スキップも可能なので

\([ \text{new\_reach} = \text{old\_reach} \;\;|\;\; \text{shifted} ]\)

とすればよいです。

これなら 1 回の更新を、配列全体を 1 マスずつ見るよりずっと速く処理できます。

アルゴリズム

1. 入力を読む。
2. もしバリケードに \(0\) が含まれていれば、答えは \(0\)。
3. \(0\) の左で最も近いバリケードを \(L\)、右で最も近いバリケードを \(R\) とする。
4. \(S=\sum |D_i|\) を求め、考える整数座標範囲を
   • \(lo = \max(-S, L+1)\)（左側にバリケードがなければ \(-S\)）
   • \(hi = \min(S, R-1)\)（右側にバリケードがなければ \(S\)） とする。
5. bitset を用意し、初期状態として座標 \(0\) だけ到達可能にする。
6. 各 \(D_i\) について：
   • 現在の bitset を old とする
   • \(D_i > 0\) なら old << D_i
   • \(D_i < 0\) なら old >> (-D_i)
   • 範囲外の bit は落とす
   • old との OR を取る（スキップ可能なので）
7. 最後に、到達可能な最大座標を出力する。

計算量

\(S=\sum |D_i|\)、\(W=hi-lo+1\) とすると \(W \le 2S+1 \le 100001\) です。

• 時間計算量: \(O\!\left(M + N \cdot \frac{W}{w}\right)\)
  ここで \(w\) は機械語 1 語あたりの bit 数です。
  bitset を使わない素朴 DP の \(O(NW)\) より高速です。
• 空間計算量: \(O(W)\) bit

実装のポイント

• \(0\) にバリケードがある場合は即座に \(0\) を出力します。

• bitset の添字と実際の座標を対応させるために、offset = -lo を使っています。

  • bit offset が座標 \(0\)

• 正のシフト << は上位に不要な bit がはみ出すので、mask で必ず削ります。

• 負の移動は右シフト >> で表せます。

• 更新時に old = reach を保存してから使うのは、1 つのプランを 2 回以上使わないためです。

• 最後の答えは、立っている bit のうち最上位のものを使って \([ \text{answer} = lo + (\text{highest\_bit\_index}) ]\) として求められます。

  ソースコード

import sys

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, M = data[0], data[1]
    D = data[2:2 + N]
    X = data[2 + N:2 + N + M]

    if 0 in X:
        print(0)
        return

    INF = 10**18
    L = -INF
    R = INF

    for x in X:
        if x < 0:
            if x > L:
                L = x
        else:  # x > 0
            if x < R:
                R = x

    S = sum(abs(d) for d in D)

    lo = -S if L == -INF else max(-S, L + 1)
    hi = S if R == INF else min(S, R - 1)

    width = hi - lo + 1
    mask = (1 << width) - 1
    offset = -lo

    reach = 1 << offset  # position 0

    for d in D:
        old = reach
        if d > 0:
            reach = old | ((old << d) & mask)
        else:
            reach = old | (old >> (-d))

    ans = lo + (reach.bit_length() - 1)
    print(ans)

if __name__ == "__main__":
    solve()

---

この解説は gpt-5.4-high によって生成されました。