東大文系数学 第 2 問とその拡張について

evima さんが YouTube に以下のようなものをあげておられました．

https://www.youtube.com/watch?v=KesNEfW2D9k

この記事は，これについて考えたことを述べます．

まずは元の入試問題を手で解く

原題を私が手で解いた解法を述べます．

原題は以下です：

まず，(1) です．

選んだ数を $S = \{x_1, \ldots, x_n\} \ \ (x_1 < x_2 < \cdots < x_n)$ とします．そして，$y_i = x_{i+1}-x_i \ \ (1 \leq i \leq N-1)$ とします．以下 $i$ の取る範囲は同様とします．また，他の添え字に関しても，取りうる範囲を一度明示して以降言及がない場合は同様の範囲を取るものとします．ここで，常に $y_i \geq 1$ です． 今回の場合は，任意の $i$ について $y_i \geq 2$ が成り立つ場合を数え上げます．

$x_1 = 1$ で，$x_N \leq 2N$ ですから，$1+y_1+\cdots+y_{N-1} \leq 2N \Leftrightarrow y_1+\cdots+y_{N-1} \leq 2N-1$ です．$y_i' = y_i-2$ なる変数変換を行うと，

$$ \begin{eqnarray} \left\{ \begin{array}{l} y_1' + \cdots + y_{N-1}' \leq 1\\ y_i' \geq 0 \end{array} \right. \end{eqnarray}\\ $$

なる非負整数解 $y_i'$ の個数を数え上げればよく，上の不等式が $0$ と等しいときはすべて $0$ の $1$ 通り，$1$ と等しいときは $N-1$ 個のうちいずれか $1$ つが $1$ でその他が $0$ のもの $N-1$ 通りなので，合わせて $N$ 通り が答です．

次に (2) です．

先と同様に
$$ \begin{eqnarray} \left\{ \begin{array}{l} y_1+\cdots+y_{N-1} \leq 2N-1 \\ y_i \geq 1 \end{array} \right. \end{eqnarray} $$
の整数解として考えます．$y_i$ を $i$ の小さい順に並べたとき，$1$ が $N-3$ 個連続する箇所を少なくとも $1$ つ含むような整数解の個数を数え上げたいです．包除原理 (和集合の要素数を積集合の要素数で表示する公式) を使います．

すなわち，$y_j\ \ (1 \leq j \leq 3)$ を先頭としてそこから $N-3$ 個 $1$ が連続するような整数解の集合を $A_j$ とします ($N \geq 5$ なので $N-1 \geq 4$ です)．有限集合 $S$ の要素数を $n(S)$ と表すと，数え上げたいものは $n(A_1 \cup A_2 \cup A_3)$ であり，よく知られる公式から，

$$ n(A_1 \cup A_2 \cup A_3) = n(A_1)+n(A_2)+n(A_3)-n(A_1 \cap A_2) - n(A_1 \cap A_3) - n(A_2 \cap A_3) + n(A_1 \cap A_2 \cap A_3) $$

です．$n(A_j)$ は状況としては同じなので，$n(A_1)$ の状況のみ考えます．すると，

$ \begin{eqnarray} \left\{ \begin{array}{l} (N-3) \times 1 + y_{N-2} + y_{N-1} \leq 2N-1 \\ y_{N-2},\ y_{N-1} \geq 1 \end{array} \right. \end{eqnarray} $

$\Leftrightarrow \begin{eqnarray} \left\{ \begin{array}{l} y_{N-2} + y_{N-1} \leq N+2 \\ y_{N-2},\ y_{N-1} \geq 1 \end{array} \right. \end{eqnarray} $

$y_i' = y_i-1$ と変数変換して，

$\Leftrightarrow \begin{eqnarray} \left\{ \begin{array}{l} y_{N-2}' + y_{N-1}' \leq N \\ y_{N-2}',\ y_{N-1}' \geq 0 \end{array} \right. \end{eqnarray} $

の整数解を数え上げればよいです．これはよく知られているように $1$ が $N$ 個並んでいて仕切りが $2$ 個あって，それらを並び替えればよい (非負整数の変数をもう一つ導入して上の不等式を等式にできます) ので，組み合わせの場合の数から ${}_{N+2}\mathrm{C}_{2} = \frac{(N+2)(N+1)}{2}$ 通りです．

次に $2$ つの集合の積集合の要素数を考えます．このうち，$n(A_1 \cap A_3)$ は $N \geq 5$ を加味するとすべてが $1$ の $1$ 通りなので除外します．その他の $2$ つは対等なので，$n(A_1 \cap A_2)$ を考えます．これは，

$ \begin{eqnarray} \left\{ \begin{array}{l} (N-2) \times 1 + y_{N-1} \leq 2N-1 \\ y_{N-1} \geq 1 \end{array} \right. \end{eqnarray} $

$\Leftrightarrow \begin{eqnarray} \left\{ \begin{array}{l} y_{N-1} \leq N+1 \\ y_{N-1} \geq 1 \end{array} \right. \end{eqnarray} $

の整数解を数えればよく，自明に $N+1$ 通りです．

最後に $n(A_1 \cap A_2 \cap A_3)$ ですが，これもすべてが $1$ の $1$ 通りです．

以上から，

$$ n(A_1 \cup A_2 \cup A_3) = \frac{(N+2)(N+1)}{2} \times 3 - 2(N+1) - 1 + 1\\ = \frac{3N^2+5N+2}{2} $$

です．したがって答は $\frac{3N^2+5N+2}{2}$ 通り です．

拡張について

問題と採点システムは https://yukicoder.me/problems/no/1414 にあります．以下に拡張問題を再掲します：

さて，想定解は動画にある通り同様に包除原理で $O(N)$ で解けるわけですが，先ほどの手による解法と同様にやると都合が悪いです (悪いのではないかとぼくは思いました)．というのも，「$M$ 個の場所のうち左から $i\ \ (1 \leq i \leq M)$ 番目を先頭として連続で $1$ が並んでいるような整数解の集合」を考えてしまうと，独立でない集合が出てきてしまって，対称性が失われ厄介です．そこで，捉え方を変えます．evima さんの動画に倣って $M$ 個の相異なる整数を選ぶことを，$N$ 個の場所があって $M$ 個を黒く，$N-M$ 個を白く塗ることと言い換えます．

ここで，さらに，$N-M$ 個の白い場所を並べておいて，その (両端を含む) $N-M+1$ 個の間隙に合計 $M$ 個の黒い場所を挿入するととらえ直します．$N-M+1$ 個のうち，左から $i \ \ (1 \leq i \leq N-M+1)$ 番目の黒い連結成分が $K$ 個以上であるような黒い箇所の挿入の仕方 (整数の選び方) の集合を $A_i$ とします．このように数え上げる集合を考えれば，互いに独立であるため対称性から線形時間に落ちます．包除原理は集合の個数が増えても同様に成り立ちます (詳しくは https://mathtrain.jp/hojo 参照)．そこで，$n(A_{i_1} \cap \cdots \cap A_{i_k}) \ \ (i_1 < \cdots < i_k)$ を計算してみましょう． $k$ は $M-k*K \geq 0$ の範囲で動くものとします．$k*K$ 個を $M$ 個の中からあらかじめ除いておいて，$M-k*K$ 個を自由に $N-M+1$ 箇所に分配すればよく，これは，$M-k*K$ 個 $1$ があって，$N-M$ 個しきりがあり，それらの組み合わせなので，${}_{N-k*K} \mathrm{C}_{N-M}$ 通りです．これは $k$ のみに依存し，$(i_1, \ldots, i_k)$ には依存しないので，添え字の選び方 $2^{N-M+1}$ 通りを選ばれた添え字の数ごとにまとめて $O(N)$ で計算することができます．すなわち組み合わせ ${}_{N-M+1} \mathrm{C}_{k}$ をかければよく，答えは
$$ \sum_{k=1}^{N-M+1} (-1)^{k+1} {}_{N-M+1} \mathrm{C}_{k} \times {}_{N-k*K} \mathrm{C}_{N-M} $$
を $\mathrm{mod}\ 998244353$ (素数) で計算すればよいです．ただし，$M-k*K \geq 0$ の範囲外においては組み合わせは 0 と定義します．素数の剰余環 $\mathbb{Z}/p\mathbb{Z}$ は体となり逆元は Fermat の小定理で計算可能なのでその上での組みあわせの計算も容易に計算可能です (これは競技プログラミングではよくやる話です．詳しくは https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a 参照)．

終わりに

evima さんの動画は簡潔すぎて，(競技プログラミングをさぼっていた自分には特に) 行間を埋めるだけで学びが多いです．連結成分を一つにつぶす，挿入を考えるというのは (玄人にとっては自明なんでしょうが) それをやるだけの問題が AtCoder 難易度 青 diff (結構難しい) に分類されていた気がするので，特殊な訓練を受けていないと一般人には無理だと思います．

evima さんの動画はいつもすばらしく，陰ながら応援しております．この記事が動画を楽しむ一助となれば幸いです．evima ラボ，皆さんチャンネル登録しましょう．

問題の掲載等何か問題があればご一報ください．