概要

各ボールの重さに基づいて、階段状のマス目上でどこまで転がるかをシミュレートする問題。

考察

ボールがマス \(1\) から順に転がっていくとき、停止するのは「そのボールの重さ \(B_j\) が越えられない最初の段差」の手前のマスです。
つまり、ボールが止まる位置は「\(W_1, W_2, ..., W_{M-1}\) の中で、左から見て初めて \(B_j\) より大きい値が現れる場所」と一致します。

しかし、毎回先頭から順に比較していたら、最悪の場合 \(O(M)\) かかり、全体で \(O(NM)\) となって間に合いません（\(N, M \sim 2 \times 10^5\) なので最大 \(4 \times 10^{10}\) 回の計算が必要）。
そこで、「あるボールがどこまで進めるか」を高速に求めることを考えます。

重要な観察として、各マス \(i\) に到達できるかどうかは、そのマスまでの全ての段差 \(W_1\) から \(W_{i-1}\) のうちの最大値とボールの重さを比較すればよい、という点があります。
つまり、各 \(i\) に対して「\(W_1\) から \(W_{i-1}\) までの最大値」を前計算しておけば、各ボールごとに二分探索を使って停止位置を求めることができます。

このように、累積最大値を前処理しておき、二分探索を行うことで効率よく答えを求められます。

アルゴリズム

1. 入力から段差の重さ \(W_1, ..., W_{M-1}\) とボールの重さ \(B_1, ..., B_N\) を読み込む。
2. 配列 max_w を用意し、max_w[i] に \(W_1\) から \(W_i\) までの最大値を格納する（累積最大値）。
3. 各ボールの重さ \(B_j\) に対して、max_w 内で「\(B_j\) 以上となる最大のインデックス」を二分探索で求める。
4. そのインデックス + 2（1-basedかつ次のマスが止まる位置）が答えとなる。

例えば： - \(W = [3, 1, 4]\) のとき - max_w = [3, 3, 4] - ボールの重さが \(5\) なら、bisect.bisect_right(max_w, 5) → 3 → マス 4 で停止

計算量

• 時間計算量: \(O(M + N \log M)\)
  • 累積最大値の前計算に \(O(M)\)
  • 各ボールに対する二分探索に \(O(N \log M)\)
• 空間計算量: \(O(M + N)\)
  • 入力データおよび累積最大値配列に使用

実装のポイント

• bisect.bisect_right は「超える最初の位置」を返すので、適切にインデックス変換する必要がある。
• 入力を高速に読み込むために sys.stdin.read を使用している。
• 結果は一旦リストにためて最後にまとめて出力することで高速化している。

## ソースコード

```python
import bisect
import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    W = list(map(int, data[2:M+1]))
    B = list(map(int, data[M+1:M+1+N]))
    
    # 各ボールがどこまで転がれるかを計算
    # Wの累積最大値を前計算しておくと効率的
    max_w = [0] * (M - 1)
    max_w[0] = W[0]
    for i in range(1, M - 1):
        max_w[i] = max(max_w[i - 1], W[i])
    
    result = []
    for b in B:
        # max_wの中で b以上となる最大のindex+1 (0-based -> 1-based)
        pos = bisect.bisect_right(max_w, b)
        result.append(str(pos + 1))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。