概要

数直線上で座標 \(0\) からスタートし、\(N\) 個の移動プランを順に検討してバリケードに衝突しないプランを選び、最終座標を最大化する問題です。Python の多倍長整数をビットセットとして用い、到達可能な座標の集合を一括管理します。

考察

到達可能座標の範囲が狭い

各プランの変位の絶対値の総和が \(\sum |D_i| \leq 5 \times 10^4\) であるため、座標 \(0\) からどのようにプランを選んでも、到達可能な座標は \([-50000, 50000]\) の範囲に収まります。これは高々 \(100001\) 個の整数座標です。

素朴な DP では？

「現在の到達可能座標の集合」を管理する DP を考えると、各プランについて集合の各要素に対して「バリケードに衝突するか」を判定する必要があります。集合サイズを \(S\)（最大 \(100001\)）、プラン数を \(N\) とすると、素朴には各プランで \(O(S \times |D_i|)\) かかり、合計 \(O(S \times \sum |D_i|)\) となります。これは \(100001 \times 50000 = 5 \times 10^9\) 程度で、普通にループすると TLE です。

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

Python の多倍長整数はビット演算が可能で、1 ビットが 1 つの座標に対応するビットセットとして使えます。ビットシフトや OR 演算は内部的にワードサイズ \(w = 64\) ビット単位で処理されるため、\(O(S/w)\) で動作し、定数倍が約 \(1/64\) になります。

アルゴリズム

OFFSET = 50000 として、座標 \(x\) をビット位置 \(x + \text{OFFSET}\) に対応させます。

1. バリケードのビットセット barricade_bits を構築：座標 \(X_j\) が範囲内ならビット \((X_j + \text{OFFSET})\) を立てる。

2. 到達可能集合 reachable を初期化：ビット \(\text{OFFSET}\)（座標 \(0\)）のみを立てる。

3. 各プラン \(d = D_i\) について：

   • \(d > 0\) の場合：座標 \(s\) から \(s + d\) へ移動する。衝突条件は「\(s, s+1, \ldots, s+d\) のいずれかにバリケードがある」こと。
     • blocked を計算：barricade_bits を \(0, 1, \ldots, d\) ビット右シフトした結果を全て OR する。すると blocked のビット \(p\) は「座標 \(p\) から \(p + d\) の区間にバリケードがあるか」を表す。
     • can_move = reachable & ~blocked（到達可能かつ衝突しない座標の集合）
     • reachable |= (can_move << d)（移動後の座標を追加）
   • \(d < 0\) の場合（\(ad = -d\)）：同様に左シフトで blocked を計算し、右シフトで移動を表現。

4. reachable の最上位ビットの位置から OFFSET を引いたものが答え。

具体例：座標 \(\{-1, 0, 2\}\) が到達可能で \(d = 3\)、座標 \(1\) にバリケードがある場合、座標 \(-1\) と \(0\) は区間 \([-1, 2]\), \([0, 3]\) にバリケード（座標 \(1\)）を含むのでブロックされ、座標 \(2\) のみが移動可能で座標 \(5\) に到達します。

計算量

• 時間計算量: \(O\!\left(\dfrac{S \cdot \sum |D_i|}{w}\right)\)
  • \(S = 100001\)、\(\sum |D_i| \leq 50000\)、\(w = 64\) で約 \(7.8 \times 10^7\) 程度
• 空間計算量: \(O(S + M)\)
  • ビットセットのサイズ \(O(S/w)\) ワード、バリケードの読み込みに \(O(M)\)

実装のポイント

• Python の多倍長整数がビットセット代わり：C++ の bitset に相当する操作を、Python では巨大整数のビット演算で実現できます。<<, >>, |, &, ~ が全てワード単位で高速に動作します。

• 範囲外のバリケードは無視：座標が \([-50000, 50000]\) 外のバリケードは到達不可能なので読み飛ばします。

• blocked の構築：\(|d|+1\) 回のシフト・OR で区間内のバリケード存在判定をまとめて行うのが核心的なテクニックです。これにより各座標ごとに独立にチェックする必要がなくなります。

• 最終的な答え：reachable.bit_length() - 1 が最上位ビット位置（= 最大到達座標 + OFFSET）なので、OFFSET を引けば座標が得られます。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    D = []
    for i in range(N):
        D.append(int(data[idx])); idx += 1
    
    OFFSET = 50000
    
    barricade_bits = 0
    for j in range(M):
        x = int(data[idx]); idx += 1
        if -50000 <= x <= 50000:
            barricade_bits |= (1 << (x + OFFSET))
    
    reachable = 1 << OFFSET  # start at position 0
    
    for d in D:
        if d > 0:
            blocked = 0
            for k in range(d + 1):
                blocked |= (barricade_bits >> k)
            can_move = reachable & ~blocked
            reachable |= (can_move << d)
        else:
            ad = -d
            blocked = 0
            for k in range(ad + 1):
                blocked |= (barricade_bits << k)
            can_move = reachable & ~blocked
            reachable |= (can_move >> ad)
    
    # Maximum set bit gives maximum reachable position
    ans = reachable.bit_length() - 1 - OFFSET
    print(ans)

main()

この解説は claude4.6opus-thinking によって生成されました。