AtCoder精選良問「D - Coloring Dominoes」Diff 1165

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

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

問題リンク

D - Coloring Dominoes

問題概要

2xNのマス目にN個のドミノを敷き詰めることを考える。
ドミノは1x2または2x1のマス目を覆い、その状態はアルファベット大文字もしくは小文字で与えられる。

aac
bbc

このようなときはaとbが1x2、cが2x1のドミノである、ということになる。

各ドミノを赤色、水色、緑色の3色で塗る。辺で接しているドミノは異なる色で塗るというルール。塗り方が何通りあるかをmod 1000000007で求める。

考え方

まず、ドミノは正しく並んでいるので、この２通りしかない。

// 縦型
A
A
// 横型
BB
CC

つまり、このブロックの組み合わせは以下の４通り。

// 縦 => 縦
A B
A B
// 縦 => 横
A BB
A CC
// 横 => 縦
AA B
CC B
// 横 => 横
AA BB
CC DD

ドミノごとに色の通り数を考えると頭がこんがらがってくる。
なので、左のブロックの色が決まっているときに、右のブロックが何通り塗れるか、という風に考える。

縦 => 縦：
２通り。前に使った色以外塗れる。

縦 => 横：
２通り。

R BB
R GG

R GG
R BB

横 => 縦：
1通り。
既に横ブロック二つで２色使われているので、１色しか塗れない。

横 => 横
3通り。

RR BB
BB RR

RR GG
BB RR

RR BB 
BB GG

あとはこの条件で余りを取りながら答えをかけていく感じで実装する。

実装

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

function main() {
    const n = nextNum()
    const ue = next()
    const sita = next()
    let ans = 1n
    const mod = 10n ** 9n + 7n
    let start = 0
    // 縦型の場合、最初は三通り
    if (ue[0] == sita[0]) {
        start = 1
        ans = 3n
    } else {
        // 横型の場合は上と下の組み合わせで6通り
        start = 2
        ans = 6n
    }
    let i = start
    while (i < n) {
        // 今が縦型
        if (ue[i] == sita[i]) {
            if (ue[i - 1] == sita[i - 1]) {
                // 縦=>縦
                ans *= 2n
            }
            // インデックスを一つ進める　※横=>縦は答えが変化せず
            i += 1
        } else {

            if (ue[i - 1] == sita[i - 1]) {
                // 横=>縦
                ans *= 2n

            } else {
                // 横=>横
                ans *= 3n
            }
            // 横型のためインデックスを二つ進める
            i += 2
        }
        // 余りを取る
        ans %= mod
    }
    log(String(ans % mod))
}

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