AtCoder精選良問「D - Lamp」Diff 1103

この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。

AtCoder 精選良問集 Diff 茶後半～水前半｜Qlitre｜note

問題リンク

D - Lamp

問題概要

H行W列の" . " もしくは" # "の文字列からなるグリッドが与えられる。
" . "ときは何も置かれておらず、" # "のときは障害物がある。
何も置かれていないマスにランプを設置すると、上下左右の障害物の手前までのマスが照らされる。
ランプを設置した際に照らされるマスの最大数を答える問題。

制約：

• H (1≤H≤2000)

• W (1≤W≤2000)

• " . "のマスは最低１つある

考え方

むかしやっていたボンバーマンの火力マックス爆弾を思い出した。
確かあれも爆弾を設置した場所から十字に極限まで破壊する、というような性能。

ボンバーマンの話は置いておこう。
とりあえず、十字にいけるところまでいくんだな、ということをまずは問題文を読んで理解する。

次に制約を見てみる。H、Wの制約は2000と結構大きい。
愚直に考えると、全探索すると答えが出る。
何も置かれていないマスにあたったら上下左右を全て調べればいい。

ただ、明らかに何回も無駄に数えるマスが出てくるので、間に合いそうな感じがしない。

すこし工夫する必要がある。
横方向と縦方向に分割して照らすことができるマスを管理してみたらどうだろう。

例えばこういうマスがあったとする。

#.#
..#
#..

対してこういう配列を作ってみる。

yoko =
    [[0, 1, 0],
    [2, 2, 0],
    [0, 2, 2]]
tate =
    [[0, 3, 0],
    [1, 3, 0],
    [0, 3, 1]]

あるマスのポジションにおいた際に、横と縦でそれぞれで照らされるマス数を記録してみた。
あとは各マスを全探索して、yoko[i][j]＋tate[i][j]-1をすれば答え。
そのマス自身が重複して数えられるので、-1をする。

肝心の計算量はどうだろう。
上のような配列を作るには一旦個数を記録して逆順でたどる必要がある。

...#..

まずは、個数を記録する。

[1,2,3,0,1,2]

次に逆から見て、大きい数字を取っていく。0の時は障害物なので0のまま。

[3,3,3,0,2,2]

なので戻りの動作が発生する。念頭において計算をしてみる。

HとWの制約は最大で2,000。
yokoとtateの記録をするのにそれぞれ、2,000 x (2,000 x 2)だから8,000,000か。
併せて16,000,000回。最後の探索の2,000 x 2,000のループを足して20,000,000ほど。キツイ印象があるが、これはぎりぎりいけるという範囲の数字。

実装

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";


function main() {
    const [h, w] = nextNums(2)
    const data: string[][] = []
    // 横方向に対していくつ照らせるかを管理
    const yoko: number[][] = []
    // 縦方向に対していくつ照らせるかを管理
    const tate: number[][] = []
    for (let i = 0; i < h; i++) {
        const arr = next().split('')
        data.push(arr)
        const yokoArr = new Array(w).fill(0)
        const tateArr = new Array(w).fill(0)
        yoko.push(yokoArr)
        tate.push(tateArr)
    }
    // yokoの記録作業
    for (let i = 0; i < h; i++) {
        let cnt = 0
        for (let j = 0; j < w; j++) {
            if (data[i][j] == '.') {
                cnt++
            } else {
                cnt = 0
            }
            yoko[i][j] = cnt
        }
        for (let j = w - 2; j > -1; j--) {
            if (data[i][j] == '#') continue
            if (yoko[i][j + 1] != 0) {
                yoko[i][j] = yoko[i][j + 1]
            }
        }
    }
    // 縦の記録作業
    for (let j = 0; j < w; j++) {
        let cnt = 0
        for (let i = 0; i < h; i++) {
            if (data[i][j] == '.') {
                cnt++
            } else {
                cnt = 0
            }
            tate[i][j] = cnt
        }
        for (let i = h - 2; i > -1; i--) {
            if (data[i][j] == '#') continue
            if (tate[i + 1][j] != 0) {
                tate[i][j] = tate[i + 1][j]
            }
        }
    }
    let ans = -1
    // 全探索して最大の箇所を探す
    for (let i = 0; i < h; i++) {
        for (let j = 0; j < w; j++) {
            ans = Math.max(ans, yoko[i][j] + tate[i][j] - 1)
        }
    }
    log(ans)
}

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

function next() {
    return inputArray[currentIndex++];
}
function nextNum() {
    return +next();
}
function nextBigInt() {
    return BigInt(next());
}
function nexts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = next();
    return arr;
}
function nextNums(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextNum();
    return arr;
}
function nextBigInts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextBigInt();
    return arr;
}


// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
    const stream = createInterface({
        input: process.stdin,
        output: process.stdout,
    });
    stream.on("line", (line) => {
        inputs += line;
        inputs += "\n";
    });
    stream.on("close", () => {
        inputArray = inputs.split(/\s/);
        main();
    });
} else {
    inputs = fs.readFileSync("/dev/stdin", "utf8");
    inputArray = inputs.split(/\s/);
    main();
}