結果

問題 No.274 The Wall
コンテスト
ユーザー Kilisame
提出日時 2016-06-13 15:53:00
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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