AtCoder精選良問「B - Colorful Lines」Diff 576

2023年5月20日 12:57

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

問題リンク

問題概要

H×Wのマス目が与えられ、その初期状態ではどのマスにも色は塗られていない。
その後、1からCまでのC種類の色が用意され、これらの色を使ってマス目に色を塗ることを考える。

色を塗る工程はQ個のクエリとして与えられ、各クエリは整数ti, ni, ciで構成される。
ここで、tiが1のときはni行目のマスを全て色ciで塗り、tiが2のときはni列目のマスを全て色ciで塗るという操作を行う。また、あるマスを色cで塗ると、そのマスの色は直前の状態に関係なく常に色cへと変化する。

色を塗る工程がすべて完了したときに、それぞれの色（1, 2, ..., C）で塗られているマスの数を求める。

考え方

このマガジンで初のARCの問題となる。
Diffは576となっているが、ARC補正みたいなものがあるのか？800まではいかないと思うが、感覚的には700くらいはあるように思った。面白い問題だと思ったので、紹介したい。

まずは入力例１をみてみる。

このクエリが与えられた際に、マスの色は下記のように変化をする。

.....   66666   66666   64666   64626   22222
.....   .....   .....   .4...   .4.2.   .4.2.
.....   .....   33333   34333   34323   34323
.....   .....   .....   .4...   .4.2.   .4.2.

愚直にシミュレートすれば答えを出すことができるが、HとWは10^9までとおおきいので、間違いなくTLEになる。

では、順番に各色ごとに何個あるか考えたらどうだろう。

愚直シミュレーションよりはましに思えるが、すこし考えると、これも厳しい。既に塗ってある色の上書きという動作があるので、既に塗ってある色をデクリメントしなければいけない。

こういう時は「後ろから考える」というテクニックを使う。
上の例で行くと、最後に１行目に2が塗られている。そのため、2は確実に1行目に塗られている。ここで１行目は既に使われていると、記録をする。

次に一個前の４列目に2を塗るという動作について。
１行目に既に２が塗られているため、行数 - 既に塗られている行数だけ、塗れる。

これを一番最初まで続けると答えになる。一般化すると、

行を塗るとき：

その行が使われていたら０
(列数 - 既に使われている列数)を塗る

列を塗るとき：

その列が既に使われていた0
(行数 - 既に使われている行数)を塗る

実装

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

function main() {
    const [h, w, c, q] = nextBigInts(4)
    const queries: bigint[][] = []
    for (let i = 0n; i < q; i++) {
        const arr = nextBigInts(3)
        queries.push(arr)
    }
    // 使用した行
    const rowUsed: Set<bigint> = new Set()
    // 使用した列
    const columnUsed: Set<bigint> = new Set()
    // クエリをひっくり返す
    queries.reverse()
    // 答え
    const ans: bigint[] = new Array(Number(c + 1n)).fill(0n)
    for (const elm of queries) {
        const [t, n, color] = elm
        if (t == 1n) {
            // 使われたらスキップ
            if (rowUsed.has(n)) continue
            // 使ったことを記録
            rowUsed.add(n)
            // 列数 - 使われている列数を足す
            const used = BigInt(columnUsed.size)
            ans[Number(color)] += BigInt(w) - BigInt(used)
        }
        if (t == 2n) {
            if (columnUsed.has(n)) continue
            columnUsed.add(n)
            const used = BigInt(rowUsed.size) | 0n
            ans[Number(color)] += h - used
        }
    }
    // 一旦文字列に直す
    const stringArr = ans.map((value) => value.toString());
    // 出力
    log(stringArr.slice(1).join(' '))
}

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();
}

この記事が気に入ったらサポートをしてみませんか？