[yukicoder] No.607 開通777年記念

問題

No.607 開通777年記念 - yukicoder

しゃくとり法を使う問題です。この問題を解くためにしゃくとり法について調べ、AOJの問題を解いたりしていました。

yamakasa3.hatenablog.com

考え方

配列は乗客の増減値が与えられるので、累積和を用いて、各車両の乗客数の値を持つ配列を作成します。

具体的には、それぞれの列に対して累積和と取っていくことになります。

乗客数の二次元配列が作成できれば、あとはしゃくとり法を使うだけです。

コード

import java.util.Scanner;

public class Exec0607 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int[][]a = new int[M][N];
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                a[i][j] = scan.nextInt();
            }
        }
        scan.close();
        int[][]b = new int[M + 1][N];

        for(int i = 1; i <= M; i++) {
            for(int j = 0; j < N; j++) {
                b[i][j] += b[i - 1][j] + a[i - 1][j];
            }
        }

        for(int i = 1; i <= M; i++) {
            int right = 0;
            int sum = 0;
            for(int left = 0; left < N; left++) {
                while(right < N && sum < 777) {
                    sum += b[i][right];
                    right++;
                }
                if(sum == 777) {
                    System.out.println("YES");
                    System.exit(0);
                }
                if(left == right) {
                    right++;
                }else {
                    sum -= b[i][left];
                }
            }
        }

        System.out.println("NO");
    }
}