サイズ d の正十二角形を作れる組み合わせの数を求める C++ プログラム

問題概要

整数 d が与えられたとします。ここで、一辺の長さが 1 の正方形タイルと正三角形タイルが無限枚あるものと考えます。これらのタイルを組み合わせて、一辺の長さが d の正十二角形（12 辺形）を作るとき、その作り方が何通りあるかを求めるのがこの問題です。答えが非常に大きくなる場合は、998244353 で割った余りを返します。

アプローチ

この問題は、二項係数を利用することで効率的に解くことができます。結論から言うと、求めるべき答えは C(2d−1, d−1)、すなわち「2d−1 個の中から d−1 個を選ぶ組み合わせの総数」です。

階乗を直接計算すると値が急激に大きくなりオーバーフローしやすいため、このプログラムでは分子と分母を掛け算しながら並行して更新し、最後に割り算を行う手法を採っています。

解法の手順

b := 2d − 1
c := 1
i を 2 から d − 1 まで 1 ずつ増やしながら以下を繰り返す：
    b := b × (2d − i)
    c := c × i
return b ÷ c

ループが終了した時点で、b には (2d−1) × (2d−2) × … × (d+1) が、c には (d−1)! が格納されており、両者の商が求める組み合わせの数になります。

コードのポイント

• (d << 1) はビットシフト演算で、「d を 2 倍する」ことを意味します。
• ループを d 回回すだけなので、計算量は O(d) と非常に効率的です。
• d が大きい場合は、問題文にある通り 998244353 での剰余を取る処理を追加する必要があります。

C++ による実装例

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

int solve(int d){
    int b = ((d << 1) - 1);
    int c = 1;
    for (int i = 2; i < d; i++){
        b *= (d << 1) - i;
        c *= i;
    }
    return (b / c);
}

int main(){
    int d = 1;
    cout << solve(d) << endl;
}

入力

d = 1

出力

1

まとめ

本記事では、一辺の長さ 1 の正方形タイルと正三角形タイルを使って、一辺 d の正十二角形を作る方法の数を求める C++ プログラムを紹介しました。二項係数 C(2d−1, d−1) を、分子と分母を並行して計算する形で実装することで、O(d) の計算量で答えを得られる点がポイントです。競技プログラミングにおいても頻出のテクニックなので、ぜひ覚えておきましょう。