AGC033

f:id:aftercider:20190504235029p:plain

50分おくれでの参加だったんですが、結果はABの2完でした。

AにTLEで結構手こずってしまった一方、Bは実装中に閃いて比較的にすぐおわりました。

残り時間でDを解こうと思ったんですが、足りなかったですね・・・

A問題

とりあえず「毎回全探索でどのくらいのもんだろう？A問題だしいけるんじゃない？」と思って、ひたむきに実装しましたが、ABCのA問題とは違いましたね・・・

あえなくTLEでダメでした。

ということで、回答にもあった通り、チェックするマスを絞って塗っていく手法を採用してAC。

実装はとても汚い感じ（涙）

function getCell(w, h, input, W, H) {
    return input[Math.max(0, Math.min(h, H - 1))][Math.max(0, Math.min(W - 1, w))];
}

function insert(w, h, input, W, H, value) {
    input[Math.max(0, Math.min(h, H - 1))][Math.max(0, Math.min(W - 1, w))] = value;
}

function checkValid(w, h, W, H) {
    return h == Math.max(0, Math.min(h, H - 1)) && w == Math.max(0, Math.min(W - 1, w));
}

function Main(input) {
    const H = parseInt(input.shift());
    const W = parseInt(input.shift());

    isBlack = false;
    var count = 0;

    var currentMap = [];
    var targetMap = [];
    input.forEach(element => {
        currentMap.push(element.split(""));
    });

    for (var h = 0; h < H; h++) {
        for (var w = 0; w < W; w++) {
            var cell = getCell(w, h, currentMap, W, H);
            if (cell == "#") {
                if (checkValid(w - 1, h, W, H) && getCell(w - 1, h, currentMap, W, H) == ".") targetMap.push([w - 1, h]);
                if (checkValid(w + 1, h, W, H) && getCell(w + 1, h, currentMap, W, H) == ".") targetMap.push([w + 1, h]);
                if (checkValid(w, h + 1, W, H) && getCell(w, h + 1, currentMap, W, H) == ".") targetMap.push([w, h + 1]);
                if (checkValid(w, h - 1, W, H) && getCell(w, h - 1, currentMap, W, H) == ".") targetMap.push([w, h - 1]);
            }
        }
    }

    while (targetMap.length > 0) {
        var nextTarget = [];
        var lightTarget = [];
        targetMap.forEach(element => {
            if (getCell(element[0], element[1], currentMap, W, H) == ".") {
                lightTarget.push(element);
            }
            insert(element[0], element[1], currentMap, W, H, "#");
        });
        targetMap = lightTarget;
        targetMap.forEach(element => {
            var w = element[0];
            var h = element[1];
            if (checkValid(w - 1, h, W, H) && getCell(w - 1, h, currentMap, W, H) == ".") nextTarget.push([w - 1, h]);
            if (checkValid(w + 1, h, W, H) && getCell(w + 1, h, currentMap, W, H) == ".") nextTarget.push([w + 1, h]);
            if (checkValid(w, h - 1, W, H) && getCell(w, h - 1, currentMap, W, H) == ".") nextTarget.push([w, h - 1]);
            if (checkValid(w, h + 1, W, H) && getCell(w, h + 1, currentMap, W, H) == ".") nextTarget.push([w, h + 1]);
        });
        count++;
        targetMap = nextTarget;
    }

    console.log(count);
}

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

B問題

着手して最初、累積和の問題かな？と思って、累積和を作るロジックを書いていました。

途中、子供が泣いて様子を見に行った時に、「あ、これじゃだめだ」と気づき、方針転換。

その結果、シンプルなコードでACになりました。

A問題よりこっちの方が簡単だった感じ。

function Main(input) {
    const H = parseInt(input.shift());
    const W = parseInt(input.shift());
    const N = parseInt(input.shift());
    const sr = parseInt(input.shift());
    const sc = parseInt(input.shift());
    const S = input.shift();
    const T = input.shift();

    var left = sc, right = sc, top = sr, bottom = sr;

    for (var i = 0; i < N; i++) {
        var s = S.charAt(i);
        var t = T.charAt(i);
        if (s == "L") {
            left--;
        } else if (s == "R") {
            right++;
        } else if (s == "U") {
            top--;
        } else {
            bottom++;
        }
        if (left <= 0 || right > W || top <= 0 || bottom > H) {
            console.log("NO");
            return;
        }

        if (t == "L") {
            right = Math.max(1, right - 1);
        } else if (t == "R") {
            left = Math.min(W, left + 1);
        } else if (t == "U") {
            bottom = Math.max(1, bottom - 1);
        } else {
            top = Math.min(H, top + 1);
        }
    }
    console.log("YES");
}

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));