山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[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");
    }
}