1

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

724
0

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

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

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

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

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

原題は以下です:

東大文系数学 第 2 問

N5 以上の整数とする.1 以上 2N 以下の整数から,相異なる N 個の整数を選ぶ.ただし,1 は必ず選ぶこととする.選んだ数の集合を S とし,S に関する以下の条件を考える.

  • (条件 1) S は連続する 2 個の整数からなる整数を 1 つも含まない.
  • (条件 2) S は連続する N2 個の整数からなる集合を少なくとも 1 つ含む.

ただし,2 以上の整数 k に対して,連続する k 個の整数からなる集合とは,ある整数 l を用いて {l, l+1, , l+k1} と表される集合を指す.(具体例略)

  1. 条件 1 を満たすような選び方は何通りあるか.
  2. 条件 2 を満たすような選び方は何通りあるか.

まず,(1) です.

選んだ数を S={x1,,xn}  (x1<x2<<xn) とします.そして,yi=xi+1xi  (1iN1) とします.以下 i の取る範囲は同様とします.また,他の添え字に関しても,取りうる範囲を一度明示して以降言及がない場合は同様の範囲を取るものとします.ここで,常に yi1 です. 今回の場合は,任意の i について yi2 が成り立つ場合を数え上げます.

x1=1 で,xN2N ですから,1+y1++yN12Ny1++yN12N1 です.yi=yi2 なる変数変換を行うと,

{y1++yN11yi0

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

次に (2) です.

先と同様に
{y1++yN12N1yi1
の整数解として考えます.yii の小さい順に並べたとき,1N3 個連続する箇所を少なくとも 1 つ含むような整数解の個数を数え上げたいです.包除原理 (和集合の要素数を積集合の要素数で表示する公式) を使います.

すなわち,yj  (1j3) を先頭としてそこから N31 が連続するような整数解の集合を Aj とします (N5 なので N14 です).有限集合 S の要素数を n(S) と表すと,数え上げたいものは n(A1A2A3) であり,よく知られる公式から,

n(A1A2A3)=n(A1)+n(A2)+n(A3)n(A1A2)n(A1A3)n(A2A3)+n(A1A2A3)

です.n(Aj) は状況としては同じなので,n(A1) の状況のみ考えます.すると,

{(N3)×1+yN2+yN12N1yN2, yN11

{yN2+yN1N+2yN2, yN11

yi=yi1 と変数変換して,

{yN2+yN1NyN2, yN10

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

次に 2 つの集合の積集合の要素数を考えます.このうち,n(A1A3)N5 を加味するとすべてが 11 通りなので除外します.その他の 2 つは対等なので,n(A1A2) を考えます.これは,

{(N2)×1+yN12N1yN11

{yN1N+1yN11

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

最後に n(A1A2A3) ですが,これもすべてが 11 通りです.

以上から,

n(A1A2A3)=(N+2)(N+1)2×32(N+1)1+1=3N2+5N+22

です.したがって答は 3N2+5N+22 通り です.

拡張について

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

拡張問題

N, M, K を与えられた整数とする。1 以上 N 以下の整数から,相異なる M 個の整数を選ぶ。
選んだ数の集合を S とし,S に関する以下の条件を考える。

 条件:S は連続する K 個の整数からなる集合を少なくとも 1 つ含む。

(以下同様の記述)

条件を満たすような選び方は何通りあるか。この選び方の数を mod 998244353 で割った余りを解答ファイルに出力せよ。

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

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

終わりに

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

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

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

投稿日:202134
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

cain
1
724

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. まずは元の入試問題を手で解く
  2. 拡張について
  3. 終わりに