いくつかのシートに覆われていない区間に分割されることがわかります。 シートの長さが一定であることから、それぞれの区間について独立に同じ問題を解いてよいことが示せます。

以上より、問題は以下のように言い換えられます。

シートが全く設置されていない橋が \(n\) 本あります。 \(i\) 番目の橋の長さは \(l_i\) です。 各橋について、橋全体を覆うのに必要なシートの最小枚数を求め、その総和を求めてください。

長さ \(l\) の橋を覆うのに必要なシートの枚数は \(\lceil \frac{l}{W} \rceil\) です。よって \(\sum_{i=1}^{n}\lceil \frac{l_i}{W} \rceil\) を求めればよく、これは時間計算量 \(O(N)\) で求められます。

サンプルコード(C++)

#include <iostream>
#include <vector>

using ll = long long;
using namespace std;

int main(){
    int n;
    cin>>n;
    ll L,w;
    cin>>L>>w;
    ll r = 0;
    vector<ll> a(n+1,L);
    for(int i=0;i<n;i++)cin>>a[i];
    ll ans = 0L;
    for(auto x:a)
    {
        if (x > r)
            ans += (x - r + w- 1) / w;
        r = x + w;
    }
    cout<<ans<<endl;
}