累積和の計算

愚直にでも解けないことはないが計算量が増えるのは愚策、みたいな問題なので「そうそうこれこれそれっぽい」とnoob丸出しなことを言う。

まず愚直版

Main.java

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int score = 0;
        for(int i=0; i<n; i++){
            score += sc.nextInt();
            System.out.println(score);
        }
    }
}

0.63秒……かかってるなあ。（チケットないので入力は見られてない）
というかお手本でもこの方法なので「これでいいんじゃね？」感はある。

（計算式だけを見て）累積和でやってみた。

Main.java

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a, b;
        a = new int[n];
        b = new int[n+1];

        b[0] = 0;

        for(int i=0; i<n; i++){
            a[i] = sc.nextInt();
        }

        for(int i=1; i<=n; i++){
            b[i] = b[i-1] + a[i-1];
        }

        for(int i=1; i<b.length; i++){
            System.out.println(b[i]);
        }
    }
}

変わってねえ。
実装の仕方を間違えているのかもしれないが、ひとまず次の問題へ行こう。
ぶち当たってから考える。