POH! Vol.2 Java模範解答

こちらではpaiza事務局側で作成したコードを随時掲載していきます。
更新日:2014年4月30日(水)

Java: paiza事務局作成コード Vol.3 動的計画法

得点:100点
通過テストケース数:7/7

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static final char WIDGET = '1';
    static final char EMPTY = '0';

        public static void main(String[] args) {
                try (BufferedReader br = new BufferedReader(new InputStreamReader(
                                                                          System.in))) {
                        // 入力初期化
                        String[] line = br.readLine().split(" ");
                        final int H = Integer.parseInt(line[0]);
                        final int W = Integer.parseInt(line[1]);
            int[][] table = new int[310][310];
            int[][] dp = new int[310][310];
            for(int i=0;i<310;i++)for(int j=0;j<310;j++)dp[i][j] = 100100100;

            int[][] state = new int[310][310];
            for (int i = 0; i < H; i++) {
                                final String stateLine = br.readLine();
                                for (int j = 0; j < W; j++) {
                                        state[i][j] = (stateLine.charAt(j) == WIDGET) ? 1 : 0;
                                }
                        }


            for(int k = 0; k < H; k++) {
                for(int i = 0; i < H - k; i++) {
                    dp[i][0] = state[i+k][0] == 0 ? Math.min(dp[i][0], 1) : 0;
                    for(int j = 1; j < W; j++) {
                        dp[i][j] = state[i+k][j] == 0 ? Math.min(dp[i][j], dp[i][j-1]+1) : 0;
                    }
                }

                int[] hist = new int[310];
                for(int i = 0; i < H-k; i++) {
                    for(int j = 0; j < W-1; j++) {
                        if(dp[i][j+1] == 0 && dp[i][j] > 0)hist[dp[i][j]]++;
                    }
                    if(dp[i][W-1] > 0)hist[dp[i][W-1]]++;
                }

                int sum = 0;
                for(int i = 0; i < W; i++) sum += hist[i+1];
                for(int i = 0; i < W; i++) table[k+1][1] += (i+1) * hist[i+1];
                for(int i = 2; i < W+1; i++) {
                    table[k+1][i] = table[k+1][i-1] - sum;
                    sum -= hist[i-1];
                }
            }

                        int S, T;
                        final int N = Integer.parseInt(br.readLine());
                        for (int i = 0; i < N; i++){
                line = br.readLine().split(" ");
                S = Integer.parseInt(line[0]);
                T = Integer.parseInt(line[1]);
                System.out.println(table[S][T]);
            }
                } catch (Exception e) {
                        e.printStackTrace();
                }

        }

        static class Point {
                final int x, y;

                Point(final int x, final int y) {
                        this.x = x;
                        this.y = y;
                }
        }
}

Java: paiza事務局作成コード Vol.2 O(H^2W^2)

得点:71点
通過テストケース数:5/7

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static final char WIDGET = '1';
    static final char EMPTY = '0';

        public static void main(String[] args) {
                try (BufferedReader br = new BufferedReader(new InputStreamReader(
                                System.in))) {

                        // 入力初期化
                        String[] line = br.readLine().split(" ");
                        final int H = Integer.parseInt(line[0]);
                        final int W = Integer.parseInt(line[1]);

                        int[][] display = new int[310][310];
            for (int i = 0; i < H; i++) {
                                final String displayLine = br.readLine();
                                for (int j = 0; j < W; j++) {
                                        display[i+1][j+1] = (displayLine.charAt(j) == WIDGET) ? 1 : 0;
                                }
                        }

                        //累積和
                        for(int i = 0; i < H; i++) {
                                for(int j = 0; j < W; j++){
                                        display[i+1][j+1] += display[i+1][j];
                                }
                        }
                        for(int j = 0; j < W; j++){
                                for(int i = 0; i < H; i++){
                                        display[i+1][j+1] += display[i][j+1];
                                }
                        }

                        int S, T, ans = 0;
                        final int N = Integer.parseInt(br.readLine());
                        for (int z = 0; z < N; z++) {
                                final String[] widgetLine = br.readLine().split(" ");
                                S = Integer.parseInt(widgetLine[0]);
                                T = Integer.parseInt(widgetLine[1]);
                ans = 0;
                for(int i = 0; i < H-S+1; i++){
                                        for(int j = 0; j < W-T+1; j++){
                                                if(display[i+S][j+T]-display[i+S][j]-display[i][j+T]+display[i][j] == 0){
                                                        ans++;
                                                }
                                        }
                                }
                                System.out.println(ans);
                        }

                } catch (Exception e) {
                        e.printStackTrace();
                }

        }

        static class Point {
                final int x, y;

                Point(final int x, final int y) {
                        this.x = x;
                        this.y = y;
                }
        }
}

Java: paiza事務局作成コード Vol.1 O(H^3W^3)

得点:42点
通過テストケース数:3/7

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static final char WIDGET = '1';
    static final char EMPTY = '0';

    public static void main(String args[] ) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 入力初期化
        String[] line = br.readLine().split(" ");
        final int H = Integer.parseInt(line[0]);
        final int W = Integer.parseInt(line[1]);

        int[][] display = new int[310][310];
        for (int i = 0; i < H; i++) {
            final String displayLine = br.readLine();
            for (int j = 0; j < W; j++) {
                display[i][j] = (displayLine.charAt(j) == WIDGET) ? 1 : 0;
            }
        }
        int S, T, ans = 0;
        boolean flag = false;
        int w = 0, h = 0;
        final int N = Integer.parseInt(br.readLine());
        for (int z = 0; z < N; z++) {
            final String[] widgetLine = br.readLine().split(" ");
            S = Integer.parseInt(widgetLine[0]);
            T = Integer.parseInt(widgetLine[1]);
            for(int i = 0; i < H; i++){
                for(int j = 0; j < W; j++){
                    flag = true;
                    for(int k = 0; k < S; k++){
                        for(int l = 0; l < T; l++){
                            h = i+k;w = j+l;
                            if(h < H && w < W){
                                if(display[h][w] == 1){
                                    flag = false;
                                }
                            }else{
                                flag = false;
                            }
                            if(flag == false)break;
                        }
                        if(flag == false)break;
                    }
                    if(flag){
                        ans++;
                    }
                }
            }
            System.out.println(ans);
            ans = 0;
        }

    }

  static class Point {
    final int x, y;

    Point(final int x, final int y) {
      this.x = x;
      this.y = y;
    }
  }
}
ページの先頭へ戻る