結果

問題 No.274 The Wall
ユーザー KilisameKilisame
提出日時 2016-06-13 15:53:00
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 6,383 bytes
コンパイル時間 4,910 ms
コンパイル使用メモリ 85,568 KB
実行使用メモリ 51,656 KB
最終ジャッジ日時 2024-04-17 19:06:50
合計ジャッジ時間 7,689 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 124 ms
41,324 KB
testcase_01 AC 126 ms
41,040 KB
testcase_02 AC 113 ms
41,068 KB
testcase_03 AC 182 ms
42,340 KB
testcase_04 AC 128 ms
41,508 KB
testcase_05 AC 129 ms
41,892 KB
testcase_06 AC 127 ms
41,496 KB
testcase_07 AC 127 ms
41,260 KB
testcase_08 AC 131 ms
41,308 KB
testcase_09 AC 132 ms
41,492 KB
testcase_10 AC 128 ms
41,296 KB
testcase_11 AC 190 ms
43,376 KB
testcase_12 AC 192 ms
51,384 KB
testcase_13 AC 139 ms
42,080 KB
testcase_14 AC 198 ms
47,592 KB
testcase_15 AC 185 ms
47,744 KB
testcase_16 AC 183 ms
43,188 KB
testcase_17 AC 181 ms
42,900 KB
testcase_18 AC 179 ms
43,164 KB
testcase_19 AC 194 ms
47,296 KB
testcase_20 AC 204 ms
51,096 KB
testcase_21 AC 206 ms
51,428 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 198 ms
51,376 KB
testcase_25 AC 207 ms
51,656 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

/*
 * ブロック情報を読み込んだ際に、1．色つきブロック数の多い順にソート 2.ブロックの順方向と逆方向、より色つきブロックの開始が左に来る方向にしたうえで、その位置が左よりのもの順にソート
 * 1本目はブロック数が最大のものを無条件に選ぶ。
 * 2本目以降は向きが固定されるものを優先的に選ぶ。
 * 向きが固定されるものを全て選択し終えてもまだブロックが置ける場合、総当たり？
 * ()
 */
public class Main {

    private static final String YES = "YES";

    private static final String NO = "NO";

    private static int n;

    private static int m;

    private static boolean[] walledBlocks;

    private static List<int[]> blocks;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = Integer.parseInt(cin.next());
        m = Integer.parseInt(cin.next());
        walledBlocks = new boolean[m];
        blocks = new ArrayList<int[]>(n);
        for (int i = 0; i < n; i++) {
            int[] block = new int[2];
            int begin = Integer.parseInt(cin.next());
            int end = Integer.parseInt(cin.next());
            block[0] = end - begin + 1;
            /* 180度回転したほうが開始位置が左にくるようであればその向きにしてからリストに詰める */
            block[1] = Math.min(begin, m - end - 1);
            blocks.add(block);
        }
        cin.close();
        /* リストをソートする。1．ブロック数の多いもの　2． */
        Collections.sort(blocks, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0] == o1[0] ? o1[1] - o2[1] : o2[0] - o1[0];
            }
        });
        execute();
    }

    private static void execute() {
        /* まずブロックの1つ目を取ってきて、そのブロックの位置をtrueに更新。処理を終えたらそのブロックを消す */
        int[] firstBlock = blocks.get(0);
        updateWalledBlocks(firstBlock[0], firstBlock[1], walledBlocks);
        blocks.remove(0);
        if (!pileUpSingleSideBlocks() || !pileUpDuplicateBlocks() || !pileUpDoubleSideBlocks(blocks, 0, walledBlocks)) {
            System.out.println(NO);
        } else {
            System.out.println(YES);
        }
    }

    private static boolean pileUpSingleSideBlocks() {
        outer: while (true) {
            Iterator<int[]> iterator = blocks.iterator();
            while (iterator.hasNext()) {
                int[] block = iterator.next();
                boolean[] canPileUp = canPileUp(block);
                if (!canPileUp[0] && !canPileUp[1]) {
                    return false;
                }
                if (canPileUp[0] && canPileUp[1]) {
                    continue;
                }
                if (canPileUp[0]) {
                    updateWalledBlocks(block[0], block[1], walledBlocks);
                } else {
                    updateWalledBlocks(block[0], m - block[0] - block[1], walledBlocks);
                }
                iterator.remove();
                continue outer;
            }
            return true;
        }
    }

    private static boolean pileUpDuplicateBlocks() {
        int[] previousBlock = {-1, -1};
        List<Integer> removeIndexes = new ArrayList<Integer>();
        for (int i = 0; i < blocks.size(); i++) {
            int[] block = blocks.get(i);
            if (block[0] == previousBlock[0] && block[1] == previousBlock[1]) {
                boolean[] canPileUp = canPileUp(block);
                if (!canPileUp[0] || !canPileUp[1]) {
                    return false;
                }
                updateWalledBlocks(block[0], block[1], walledBlocks);
                updateWalledBlocks(block[0], m - block[0] - block[1], walledBlocks);
                removeIndexes.add(i - 1);
                removeIndexes.add(i);
                continue;
            }
            previousBlock = block;
        }
        for (int i = removeIndexes.size() - 1; i >= 0; i--) {
            blocks.remove((int) removeIndexes.get(i));
        }
        return true;
    }

    private static boolean pileUpDoubleSideBlocks(List<int[]> restBlocks, int index, boolean[] walledBlocksTemp) {
        if (index >= restBlocks.size()) {
            return true;
        }
        int[] block = restBlocks.get(index);
        boolean[] canPileUp = canPileUp(block);
        if (!canPileUp[0] && !canPileUp[1]) {
            return false;
        }
        if (canPileUp[0]) {
            boolean[] copyWalled = Arrays.copyOf(walledBlocksTemp, walledBlocksTemp.length);
            updateWalledBlocks(block[0], block[1], copyWalled);
            if (pileUpDoubleSideBlocks(restBlocks, index + 1, copyWalled)) {
                return true;
            }
        }
        if (canPileUp[1]) {
            boolean[] copyWalled = Arrays.copyOf(walledBlocksTemp, walledBlocksTemp.length);
            updateWalledBlocks(block[0], m - block[0] - block[1], copyWalled);
            if (pileUpDoubleSideBlocks(restBlocks, index + 1, copyWalled)) {
                return true;
            }
        }
        return false;
    }

    private static boolean[] canPileUp(int[] block) {
        boolean[] canPileUp = new boolean[2];
        canPileUp[0] = true;
        canPileUp[1] = true;
        /* 180度回転しても同じ配置になるブロックだったら、あらかじめcanPileUp[1]をfalseとして片側のみOKにする */
        if (block[1] == m - block[0] - block[1]) {
            canPileUp[1] = false;
        }
        for (int i = 0; i < block[0]; i++) {
            if (walledBlocks[block[1] + i]) {
                canPileUp[0] = false;
            }
            if (walledBlocks[m - block[0] - block[1] + i]) {
                canPileUp[1] = false;
            }
        }
        return canPileUp;
    }

    private static void updateWalledBlocks(int length, int begin, boolean[] targetBlocks) {
        for (int i = 0; i < length; i++) {
            targetBlocks[begin + i] = true;
        }
    }
}
0