yukicoder No.607 開通777年記念

問題
電車の乗り降りが行われる中で、任意の連続する車両の区間における、乗車数の和が777人となるタイミングがあるかどうかを判定する。
自分で作った問題なので、真面目に解説をします。

解法
簡潔にいうと、乗車人数を累積和を用いて更新していきながら、更新する度に尺取り法で777人となるような連続する車両の区間があるかどうか判定する。
入力のデータは、縦M行、横N列であることに注意しよう。

手始めに、0で初期化した各車両の人数を格納する長さNの配列を用意する。

以下の操作は、M回のループを回す度に行っていく。（つまり、乗客の乗り降りが行われる度に行う。）
まずは乗車人数を更新していくことを考える。入力は一つ前の区間との差分になっているので、N個の入力を受けて、i個目の入力はi番目の配列に足すだけで良い。
次に777人の判定をしていくことを考える。今回は尺取り法での解法を紹介する。

尺取り法は、範囲の右端と左端を表す変数を用意して、範囲における特定の値が大きければ左端を進めて範囲を狭くして、特定の値を小さくする。小さくなれば、また右端を伸ばして、特定の値を調べることをする。この問題では、「範囲の要素全ての和」が特定の値に当たる。
左端と右端を表す変数left, rightを作り、rightをループで回しながら（範囲の右端を伸ばしながら）、範囲の合計が777より大きい間、leftをwhileで縮めていく（範囲の左端を縮める）。whileを抜けた時、範囲の合計は777以下になることが保証されているので、このタイミングで777人ぴったりになっているかを判定すれば良い。
また、このwhileではleft>rightとならないように注意しよう（左端と右端の位置関係より当然）。

今回の尺取り法はrightをfor文で、leftをwhileで操作したが、両方whileでやったりする人もいるので、自分が書きやすいやり方を見つけよう。

int main() {
    int N,M;
    cin>>N>>M;
    vector<int> train(N,0);  //電車の乗車数を保存する配列train[ ]
    rep(i,0,M){
        //乗車人数の更新
        rep(j,0,N){
            int x;cin>>x;
            train[j]+=x;
        }
        //尺取り法
        int left=-1,right=0,sum=0;
        for(int right=0;right<N;right++){  //右端を進めるfor文
            sum+=train[right];
            while(sum>777&&left<right){  //左端を縮めるwhile文
                left++;
                sum-=train[left];
            }
            //合計が777人であればYESを出力してプログラム終了
            if(sum==777){
                cout<<"YES"<<endl;
                return 0;
            }
        }
    }
    cout<<"NO"<<endl;
    return 0;
}