AtCoder AGC051-A Dodecagon 解説

問題

問題のリンク

1 辺の長さが $1$ の正方形・正三角形を用いて 1 辺の長さが $d$ の正 12 角形を作る方法は何通りありますか。

解説

正 12 角形の内角は 150 度なので、頂点部分は正方形と正三角形を隣り合う形で使う必要があります。…①
よって、ある頂点に注目した時、その頂点部分の埋め方は以下の実線と点線の二通りです。

また、正 12 角形の辺の部分で正方形と正三角形が隣り合うと、30 度の隙間が生まれてしまい、これは正方形と正三角形で埋めることができません。よって、辺の部分では正方形・正三角形が連続します。…②

①②から、ある頂点部分の埋め方を決めれば、以下のように外側の埋め方が確定します。

そうすると内側に 12 角形が現れます。外側の 12 角形の辺の長さが $d$ なので、内側の 12 角形の辺の長さは $d$, $d-1$, $d$, $d-1$.. です。

内側の 12 角形も①②に基づいて外側から埋められて、そうするとさらにその内側に 12 角形が現れて.. と再帰的に続きそうです。

---

再帰的に考えるとすれば、正 12 角形以外の 12 角形を考える必要も生まれてくるため、ここで一般に辺の長さが $a$, $b$, $a$, $b$.. となっている 12 角形に対する求める個数 $f(a, b)$ を考えます。

上記の図も参考に、この 12 角形の内側の 12 角形の辺の長さは以下の通りです。

• 「外側の 12 角形の正方形が接していた辺」と平行な辺：平行な辺と同じ長さ
• 「外側の 12 角形の正三角形が接していた辺」と平行な辺：平行な辺の長さ - 1

外側の頂点部分の埋め方によって $a$, $b$ どちらの辺に正方形が接するかが変わります。
よって内側の 12 角形の辺の長さは $a-1$, $b$, $a-1$, $b$.. となるか、 $a$, $b-1$, $a$, $b-1$.. となるかの 2 通りです。
内側の 12 角形の埋め方の通りはそれぞれ $f(a-1, b)$, $f(a, b-1)$ であることから、 $f(a, b) = f(a-1, b) + f(a, b-1)$ となります。

気になるのは $a-1$, $b-1$ の計算によって辺の長さが $0$ となった場合です。
これは以下の図で色を塗られた 12 角形の内側のように、正六角形が現れることを表します。この場合、この正六角形の埋め方が $f(2,0)$ 通りであると捉えることができます。

正六角形の内角は 120 度であることから、頂点部分は正三角形を隣り合う形で埋める必要があります。これと②から、正六角形の辺に接する部分は全て正三角形で埋めるしかありません。
また、埋めたその内側には辺の長さが 1 小さい正六角形が現れます。
再帰的に考えて、正六角形の埋め方は図の点線のように内部を全て正三角形で埋める 1 通りしかないことがわかります。

以上から、以下の漸化式が得られます。

$$\newcommand{\arraystretch}{1.7} f(a, b) = \left\{ \begin{array}{rcl} f(a-1, b) + f(a, b-1) & (a \gt 0 \land b \gt 0) \\ 1 & (a = 0 \lor b = 0) \end{array} \right.$$

求める答えは $f(d,d)$ です。上記を素直にメモ化再帰すると $O(d^2)$ になりますが、今回の制約 $d \leq 10^6$ では間に合いません。

小さな $a$, $b$ について $f(a,b)$を埋めてみると、以下のように、そこはかとなく二項係数を感じる表が得られます。

確かに $f(a, b)$ は「一番左上のマスから、右もしくは下の移動のみを行ってマス$(a, b)$に辿り着く経路」の個数を表していると捉えることができ、この個数は $_{a+b}\mathrm{C}_a$ です。

よって $f(a, b) = _{a+b}\mathrm{C}_a$ と単純化でき、求める答えは $_{2d}\mathrm{C}_d$ となります。
最後に、回転させて一致するものは同一のものとみなして数える必要があります。12 角形の最も外側の部分の埋め方の 2 通りは回転させると一致するため、これは区別してはならず、2 で割る必要があります。

コード

#include <atcoder/all>

#include "iostream"

using namespace atcoder;
using namespace std;

// ※ 実際の問題では求める個数を 998244353 で割ったあまりの出力が求められている
using mint = modint998244353;

int main() {
  int D;
  cin >> D;

  mint res = 1;

  for (int i = 0; i < D; ++i) {
    res *= 2 * D - i;
  }

  for (int i = 1; i <= D; ++i) {
    res /= i;
  }

  res /= 2;

  cout << res.val() << "\n";
  return 0;
}

感想

考察パートにウェイトがあって結論はシンプルなの、痺れます。

参考

• 公式解説