結果

問題 No.274 The Wall
ユーザー KilisameKilisame
提出日時 2016-06-13 15:53:00
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 6,383 bytes
コンパイル時間 2,427 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 51,420 KB
最終ジャッジ日時 2024-10-09 13:13:37
合計ジャッジ時間 7,876 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 122 ms
41,212 KB
testcase_01 AC 123 ms
40,820 KB
testcase_02 AC 122 ms
41,224 KB
testcase_03 AC 173 ms
42,512 KB
testcase_04 AC 124 ms
41,312 KB
testcase_05 AC 123 ms
41,256 KB
testcase_06 AC 125 ms
41,404 KB
testcase_07 AC 111 ms
40,024 KB
testcase_08 AC 126 ms
41,112 KB
testcase_09 AC 128 ms
41,088 KB
testcase_10 AC 131 ms
40,976 KB
testcase_11 AC 192 ms
42,920 KB
testcase_12 AC 202 ms
51,264 KB
testcase_13 AC 147 ms
41,736 KB
testcase_14 AC 195 ms
47,532 KB
testcase_15 AC 197 ms
47,484 KB
testcase_16 AC 191 ms
42,824 KB
testcase_17 AC 187 ms
43,064 KB
testcase_18 AC 185 ms
43,068 KB
testcase_19 AC 203 ms
46,832 KB
testcase_20 AC 212 ms
51,284 KB
testcase_21 AC 202 ms
50,952 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 213 ms
51,420 KB
testcase_25 AC 205 ms
51,336 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