実力判定：Sランク

実力判定：Sランク

締め切りが 2017/12/31 10:00 AM なので，その 1 分後に投稿されるように予約

【問題】
0から9の整数を、縦横それぞれN個並べた四角形があります。
左上から右下に、右あるいは下へと移動しながら、数を足していきます。
複数ある経路のうち、最小合計値となる経路をたどった場合の、合計値を答えてください。
ただし、Nは、2≦N≦20 の範囲の整数とします。# 20 ではなく 1000 だ！
 
例
567
133
502
上記の場合の全経路と合計値。
route: 56732, sum: 23
route: 56332, sum: 19
route: 56302, sum: 16
route: 51332, sum: 14
route: 51302, sum: 11
route: 51502, sum: 13
上記の場合の、最小合計値となる経路の図示。
567
133
502
最小合計値は「11」。
 
【入力】
標準入力から、複数行のデータが与えられます。縦横同じ文字数で、1つの正方形が作られます。
【出力】
最小合計値となる経路をたどった場合の合計値を、標準出力に出力します。
【入出力サンプル】
Input
567
133
502
 
Output
11
 
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

R では簡単に書けるが，時間制限に引っかかる

f = function(s) {
    x = t(sapply(s, function(t) as.integer(unlist(strsplit(t, "")))))
    n = nrow(x)
    x[1:n, 1] = cumsum(x[1:n, 1])
    x[1, 1:n] = cumsum(x[1, 1:n])
    for (i in 2:n) {
        for (j in 2:n) {
            x[i, j] = x[i, j] + min(x[i-1, j], x[i, j-1])
        }
    }
    x[n, n]
}

cat(f(readLines(file("stdin", "r"))))

Java で書き直して OK となる

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int i, m;
        int n = 0;
        int[][] x = new int[1000][1000];

        Scanner cin = new Scanner(System.in);
        String line;
        while (cin.hasNextLine()) {
            line = cin.nextLine();
            if (line.length() == 0) {
                break;
            }
            String[] ch = line.split("");
            m = ch.length - 1;
            for (i = 0; i < m; i++) {
                x[n][i] = Integer.parseInt(ch[i + 1]);
            }
            n++;
        }
        System.out.println(f(x, n));
    }

    static int f(int[][] x, int n) {
        int i, j;
        for (i = 1; i < n; i++) {
            x[i][0] += x[i - 1][0];
            x[0][i] += x[0][i - 1];
        }
        for (i = 1; i < n; i++) {
            for (j = 1; j < n; j++) {
                x[i][j] += Math.min(x[i - 1][j], x[i][j - 1]);
            }
        }
        return x[n - 1][n - 1];
    }

}