白黒のセルにドミノをすべて配置できるか判定するC++プログラム

問題の概要

5つの整数 n、k1、k2、w、b が与えられるとします。ここで、2 × n のマス目からなるボードを考えます。1行目の左端から k1 個のセル、2行目の左端から k2 個のセルは白色に塗られており、残りのセルはすべて黒色です。さらに、白いドミノ w 個と黒いドミノ b 個(いずれも 2 × 1 のサイズ)を持っています。

白いドミノは、その両方のセルが白色であり、かつ他のドミノに占有されていない場合にのみ配置できます。同様に、黒いドミノは、両方のセルが黒色で未占有の場合にのみ配置できます。ドミノは縦方向・横方向どちらにも置けるものとして、与えられた w + b 個のドミノをすべて盤上に配置できるかどうかを判定します。

たとえば、入力が n = 5、k1 = 4、k2 = 3、w = 3、b = 1 の場合、出力は True(配置可能)になります。

解法の考え方

この問題を解くポイントは、各色について「セルの総数」と「ドミノが必要とするセル数」だけを比較すればよいという点です。

• 白いドミノ1個は白色セルを2つ消費します。2 × n のボードでは、各行が連続しているため、白色セルの余りを上下の行で縦にペアにできるので、2 × w ≤ k1 + k2 が満たされれば白いドミノをすべて配置できます。

• 同様に、黒色セルの総数は (n − k1) + (n − k2) なので、2 × b ≤ (n − k1) + (n − k2) が満たされれば黒いドミノもすべて配置できます。

この2つの条件をまとめると、次のような手順になります。

if 2 * w <= (k1 + k2) and 2 * b <= (n - k1 + n - k2), then:
    return true
Otherwise
    return false

実装例(C++)

以下に、上記のロジックを実装したC++のコードを示します。

#include <bits/stdc++.h>
using namespace std;

bool solve(int n, int k1, int k2, int w, int b) {
    if (2 * w <= (k1 + k2) && 2 * b <= (n - k1 + n - k2)) {
        return true;
    }
    else {
        return false;
    }
}
int main() {
    int n = 5;
    int k1 = 4;
    int k2 = 3;
    int w = 3;
    int b = 1;
    cout << solve(n, k1, k2, w, b) << endl;
}

入力

5, 4, 3, 3, 1

出力

1

計算量について

この解法は比較演算を2回行うだけなので、時間計算量は O(1)、追加の空間計算量も O(1) となり、非常に効率的です。入力サイズが大きくなっても即座に判定できる点が魅力です。