概要

高橋君が数直線上を移動する \(N\) 個のプランを順番に検討し、バリケードに衝突しない範囲で最終的な座標を最大化する問題です。 移動距離の絶対値の総和が \(5 \times 10^4\) と比較的小さいため、座標の動く範囲が限定されている点に着目し、ビットセット（Bitset）を用いた高速な動的計画法（DP）で解くことができます。

考察

1. 座標の範囲を絞り込む

制約を見ると、\(\sum |D_i| \leq 5 \times 10^4\) とあります。高橋君は座標 \(0\) から出発するため、どのような移動をしても最終的な座標 \(s\) は \(-50000 \leq s \leq 50000\) の範囲に収まります。 この範囲外にあるバリケード \(X_j\) は無視して構いません。

2. 基本的な DP の検討

次のような DP を考えます。 - \(dp[i][s] :\) \(i\) 番目までのプランを検討したとき、座標 \(s\) にいることが可能か（真偽値）

各プラン \(D_i\) について、現在の座標 \(s\) から \(s + D_i\) へ移動する際にバリケードがないかを判定し、移動可能であれば \(dp[i][s+D_i]\) を真にします。また、プランをスキップする場合は常に \(dp[i][s]\) が引き継がれます。

しかし、状態数が \(N \times (2 \times \sum |D_i|) \approx 5 \cdot 10^4 \times 10^5 = 5 \cdot 10^9\) となり、愚直な DP では実行時間制限に間に合いません。

3. ビットセットによる高速化

「座標 \(s\) に到達可能か」という情報をビット列（Python では多倍長整数）として管理することで、複数の座標をまとめて更新できます。

• reachable: \(k\) 番目のビットが、座標 \(k - S\) に到達可能なら \(1\)
• can_move[d]: 座標 \(s\) から \(s+d\) への移動がバリケードに衝突しないなら、対応するビットが \(1\)

各ステップの遷移は以下のようになります（\(d > 0\) の場合）： reachable |= (reachable & can_move[d]) << d これにより、一度にすべての到達可能座標からの遷移を計算できます。

4. バリケード判定の高速化

ある座標 \(s\) から \(d\) だけ移動する際、\([s, s+d]\)（または \([s+d, s]\)）の間にバリケードがあるかを高速に判定する必要があります。 これは、「座標 \(s\) が、『バリケードの座標 \(X_j\) から \(-d\) から \(0\) までの範囲』に含まれるか」と言い換えられます。

具体的には、バリケードがある座標のビットを \(1\) にした bad_bits を用意し、それを \(0, 1, \dots, |d|\) だけシフトしたものの OR（和集合）を取ることで、「そこから動くと衝突する座標の集合」を効率よく計算できます。この和集合の計算には、ダブリング（Binary Lifting）に似た手法を用いることで \(O(\log |d|)\) 回のシフト演算で計算可能です。

アルゴリズム

1. 準備: 座標のオフセット \(S = \sum |D_i|\) を設定し、座標 \(x\) をビット位置 \(x + S\) に対応させます。
2. バリケードの抽出: 範囲 \([-S, S]\) に含まれるバリケードの位置を記録したビット列 bad_bits を作成します。
3. 移動可否の事前計算: 各プランに現れる各 \(D_i\) について、衝突せずに移動開始できる座標の集合 can_move[D_i] を計算します。
   • \(d > 0\) のとき: bad_bits | (bad_bits >> 1) | ... | (bad_bits >> d) の否定をとる。
   • \(d < 0\) のとき: bad_bits | (bad_bits << 1) | ... | (bad_bits << |d|) の否定をとる。
4. DP の実行:
   • reachable = 1 << S (初期座標 0)
   • 各 \(D_i\) について、reachable |= (reachable & can_move[D_i]) << D_i のように更新。
5. 回答: reachable の中で最も上位にあるビットを探し、オフセット \(S\) を引いて出力します。

計算量

• 時間計算量: \(O\left(\frac{N \cdot S}{w} + \text{distinct}(D) \cdot \frac{S}{w} \log S\right)\)
  • \(S = \sum |D_i|\), \(w\) はワードサイズ（ビット演算の高速化係数）。
  • Python の多倍長整数によるビット演算は非常に高速なため、この計算量で十分に間に合います。
• 空間計算量: \(O(M + S)\)
  • バリケードの保存と、ビットセットの保持に依存します。

実装のポイント

• ビットシフトの和集合: B | (B >> 1) | ... | (B >> k) を計算する際、k を \(1, 2, 4, \dots\) と倍々に増やしながら OR を取ることで、計算回数を \(O(k)\) から \(O(\log k)\) に削減しています。

• Python の int.bit_length(): reachable ビット列の中で最も右側（大きな座標）にある \(1\) の位置を特定するのに便利です。

• 負の座標の扱い: 数直線の負の領域を扱うため、必ず一定の値（オフセット）を足して非負のインデックスに変換する必要があります。”`python

  核心となるビットセット更新部分のイメージ

  for d in D: if d > 0: # can_move[d] は「座標 s から s+d に移動してもバリケードに当たらない s」の集合 # 該当する座標からの移動先 (<< d) と、元の座標（スキップ）の OR を取る reachable |= (reachable & can_move[d]) << d else: reachable |= (reachable & can_move[d]) >> abs(d)

  ソースコード

import sys

# Increase recursion depth just in case
sys.setrecursionlimit(200000)

def solve():
    # Using sys.stdin.read().split() to get all input at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # D_i are the next N elements
    D = [int(x) for x in input_data[2:2+N]]
    
    # X_j are the next M elements
    # M can be 0, so input_data[2+N:2+N+M] will be empty
    X = [int(x) for x in input_data[2+N:2+N+M]]
    
    # Sum of absolute values of D_i is at most 50,000
    S_max = 0
    for d in D:
        if d > 0:
            S_max += d
        else:
            S_max -= d
    
    # Coordinate range of reachable s is [-S_max, S_max]
    # Offset is S_max to map to non-negative bit indices [0, 2*S_max]
    num_bits = 2 * S_max + 1
    mask = (1 << num_bits) - 1
    
    # bad_bits: bit k is 1 if coordinate k-S_max is a barricade
    bad_bits = 0
    for x in X:
        if -S_max <= x <= S_max:
            bad_bits |= (1 << (x + S_max))
    
    # Pre-calculate can_move[d] for each distinct d
    # can_move[d] bit s is 1 if the move d from coordinate s is valid (no barricades hit)
    
    def get_union_shifts_right(B, k, mask):
        # Returns B | (B >> 1) | ... | (B >> k)
        # This uses a binary exponentiation-like trick to compute the union in O(log k) shifts
        length = k + 1
        res = 0
        current_B = B
        shift_so_far = 0
        for i in range(length.bit_length()):
            if (length >> i) & 1:
                res |= (current_B >> shift_so_far)
                shift_so_far += (1 << i)
            current_B |= (current_B >> (1 << i))
            current_B &= mask
            res &= mask
        return res

    def get_union_shifts_left(B, k, mask):
        # Returns B | (B << 1) | ... | (B << k)
        length = k + 1
        res = 0
        current_B = B
        shift_so_far = 0
        for i in range(length.bit_length()):
            if (length >> i) & 1:
                res |= (current_B << shift_so_far)
                shift_so_far += (1 << i)
            current_B |= (current_B << (1 << i))
            current_B &= mask
            res &= mask
        return res

    can_move = {}
    distinct_D = set(D)
    for d in distinct_D:
        if d > 0:
            # Plan d > 0 from s is blocked if any X_j is in [s, s+d]
            # This is equivalent to s being in [X_j-d, X_j]
            # So bit s+S_max is invalid if any bit (s+S_max) is in [X_j-d+S_max, X_j+S_max]
            invalid_D = get_union_shifts_right(bad_bits, d, mask)
        else:
            # Plan d < 0 from s is blocked if any X_j is in [s+d, s]
            # This is equivalent to s being in [X_j, X_j-d] (where -d = abs(d))
            # So bit s+S_max is invalid if any bit (s+S_max) is in [X_j+S_max, X_j+abs(d)+S_max]
            invalid_D = get_union_shifts_left(bad_bits, -d, mask)
        can_move[d] = mask & ~invalid_D
    
    # DP with bitset
    # reachable is a bitset where bit k is 1 if coordinate k-S_max is reachable
    reachable = 1 << S_max
    for d in D:
        if d > 0:
            # If no collision, we can choose to execute the plan or skip it
            # Executing moves from s to s+d, skipping stays at s
            # Bit s+S_max moves to (s+d)+S_max, which is a left shift by d
            reachable |= (reachable & can_move[d]) << d
        else:
            # Executing moves from s to s+d (d is negative), which is a right shift by abs(d)
            reachable |= (reachable & can_move[d]) >> (-d)
        # We must mask reachable to stay within bounds, although it's naturally bounded
        reachable &= mask
    
    # The answer is the maximum coordinate s such that bit s+S_max is set
    # reachable.bit_length() - 1 gives the highest bit index
    print(reachable.bit_length() - 1 - S_max)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。