この問題は二分探索により解くことができます。

重さ \(b\) のボールが少なくともマス \(p+1\) まで転がるための必要十分条件は、\(b\geq W_1\) かつ \(\dots\) かつ \(b\geq W_p\) です。この条件は \(b\geq \max(W_1,\dots,W_p)\) と表すことができます。よって、 \(b < \max(W_1,\dots,W_p)\) となる最小の \(p\) が求める答えとなります。ここで、 \(W'_i=\max(W_1,\dots,W_i)\) と定めると、 \(W_i\) は単調増加であるため、二分探索によりこの \(p\) を求めることができます。

なお、 \(W'_i=\max(W'_{i-1},W_i)\) と計算することで、 \(W'\) は \(O(M)\) で計算できます。

計算量は \(O(M+N\log M)\) となります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<int>w(m-1), b(n);
  for(int i=0; i<m-1; i++) cin >> w[i];
  for(int i=0; i<n; i++) cin >> b[i];

  for(int i=1; i<m-1; i++){
    w[i] = max(w[i-1], w[i]);
  }

  for(int i=0; i<n; i++){
    cout << (upper_bound(w.begin(), w.end(), b[i]) - w.begin() + 1) << endl;
  }
}

実装例 (Python)

from bisect import bisect_right
N, M = map(int, input().split())
W = list(map(int, input().split()))
B = list(map(int, input().split()))

for i in range(1, M-1):
  W[i] = max(W[i-1], W[i])

for b in B:
  print(bisect_right(W, b) + 1)