Baekjun-カラーペーパーを作成[java]

34391 ワード
コーディングテスト練習 航海 996週間航行 テキストリンク
質問元:https://www.acmicpc.net/problem/2630

問題の説明


DivideとConquerの問題.
下の写真を見ると分かりやすいです.

1と0の個数の問題を探して、
縦2倍の色紙を1枚の色紙にする.
1 1
1なら4個1個1個になります
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1だと8個1が1個1になるという概念

入力例 8 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 サンプル出力 9/0 7/1の数量

問題を解く

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

        int[][] board = new int[size][size];

        for (int r = 0; r < board.length; r++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int c = 0; c < board[0].length; c++)
                board[r][c] = Integer.parseInt(st.nextToken());
        }
        int divide = 1;
        int conquerSize = 0;
        for (int i = 1; i < 8; i++) {
            if (Math.pow(2, i) == size) {
                conquerSize = i;
                break;
            }
        }
        int[] conquerOne = new int[conquerSize + 1];
        int[] conquerZero = new int[conquerSize + 1];
        int conquerIndex = 0;
        while (divide <= size) {
            for (int r = 0; r < size; r += divide) {
                for (int c = 0; c < size; c += divide) {
                    if (count(board, r, c, divide) == 1) {
                        conquerOne[conquerIndex]++;
                    } else if (count(board, r, c, divide) == 0) {
                        conquerZero[conquerIndex]++;
                    }
                }
            }
            divide *= 2;
            conquerIndex++;
        }

        System.out.println(calcTotal(conquerOne));
        System.out.println(calcTotal(conquerZero));
        br.close();
    }

    public static int count(int[][] board, int startPointR, int startPointC, int divide) {
        // -1, 0, 1
        int one = 0;
        int zero = 0;
        for (int r = startPointR; r < startPointR + divide; r++) {
            for (int c = startPointC; c < startPointC + divide; c++) {
                if (board[r][c] == 1)
                    one++;
                else
                    zero++;
            }
        }
        if (one != 0 && zero == 0)
            return 0;
        else if (one == 0 && zero != 0)
            return 1;
        else
            return -1;
    }

    public static int calcTotal(int[] conquer) {
        for(int i = 1; i < conquer.length; i++)
            conquer[i - 1] = conquer[i - 1] - conquer[i] * 4;
        return IntStream.of(conquer).sum();
    }
}
私の解題過程は以下の通りです.

  • 入力を受け入れ、2 D配列を受け入れます.

  • 2 D配列のサイズを確認した後、1と0の合計数を個数で表示します.
    • サンプル入力の場合:
    8サイズの2 Dアレイ.
    0の個数[寸法が1の場合、寸法が2の場合、寸法が4の場合、寸法が8の場合]=[30,7,0]
    1の個数[寸法が1の場合、寸法が2の場合、寸法が4の場合、寸法が8の場合]=[34,8,1,0]
    4を掛けて正面に並ぶ個数を減算します.
    30 - 4 x 7 = 2
    34 - 4 x 8 = 2
    8 - 1 x 4 = 4
    0の個数=2+7=9
    1の個数=2+4+1=7

    別の解釈

    import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] arr;
    static int white, blue = 0;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        arr = new int[N][N];
        for (int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0 ; j < N ; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        square(0, 0, N);
        StringBuilder sb = new StringBuilder();
        sb.append(white + "\n");
        sb.append(blue);
        System.out.println(sb.toString());
    }

    static void square(int r, int c, int n) {
        if (allPainted(r, c, n)) {
            if (arr[r][c] == 0) {
                white++;
            } else {
                blue++;
            }
        } else {
            square(r, c, n/2);
            square(r, c + n/2, n/2);
            square(r + n/2, c, n/2);
            square(r + n/2, c + n/2, n/2);
        }
    }

    static boolean allPainted(int r, int c, int n) {
        int init = arr[r][c];
        for (int i = r ; i < r + n ; i++) {
            for (int j = c ; j < c + n ; j++) {
                if (init != arr[i][j]) return false;
            }
        }
        return true;
    }
}
    回帰で简単にできましたね.このように見ると簡単な問題のようです.難しいと思います
    [TIL] 210926
    [css]オーバーボリュームの解決