evima さんが YouTube に以下のようなものをあげておられました.
https://www.youtube.com/watch?v=KesNEfW2D9k
この記事は,これについて考えたことを述べます.
まずは元の入試問題を手で解く
原題を私が手で解いた解法を述べます.
原題は以下です:
東大文系数学 第 2 問
を 以上の整数とする. 以上 以下の整数から,相異なる 個の整数を選ぶ.ただし, は必ず選ぶこととする.選んだ数の集合を とし, に関する以下の条件を考える.
- (条件 1) は連続する 個の整数からなる整数を つも含まない.
- (条件 2) は連続する 個の整数からなる集合を少なくとも つ含む.
ただし, 以上の整数 に対して,連続する 個の整数からなる集合とは,ある整数 を用いて と表される集合を指す.(具体例略)
- 条件 1 を満たすような選び方は何通りあるか.
- 条件 2 を満たすような選び方は何通りあるか.
まず,(1) です.
選んだ数を とします.そして, とします.以下 の取る範囲は同様とします.また,他の添え字に関しても,取りうる範囲を一度明示して以降言及がない場合は同様の範囲を取るものとします.ここで,常に です. 今回の場合は,任意の について が成り立つ場合を数え上げます.
で, ですから, です. なる変数変換を行うと,
なる非負整数解 の個数を数え上げればよく,上の不等式が と等しいときはすべて の 通り, と等しいときは 個のうちいずれか つが でその他が のもの 通りなので,合わせて 通り が答です.
次に (2) です.
先と同様に
の整数解として考えます. を の小さい順に並べたとき, が 個連続する箇所を少なくとも つ含むような整数解の個数を数え上げたいです.包除原理 (和集合の要素数を積集合の要素数で表示する公式) を使います.
すなわち, を先頭としてそこから 個 が連続するような整数解の集合を とします ( なので です).有限集合 の要素数を と表すと,数え上げたいものは であり,よく知られる公式から,
です. は状況としては同じなので, の状況のみ考えます.すると,
と変数変換して,
の整数解を数え上げればよいです.これはよく知られているように が 個並んでいて仕切りが 個あって,それらを並び替えればよい (非負整数の変数をもう一つ導入して上の不等式を等式にできます) ので,組み合わせの場合の数から 通りです.
次に つの集合の積集合の要素数を考えます.このうち, は を加味するとすべてが の 通りなので除外します.その他の つは対等なので, を考えます.これは,
の整数解を数えればよく,自明に 通りです.
最後に ですが,これもすべてが の 通りです.
以上から,
です.したがって答は 通り です.
拡張について
問題と採点システムは
https://yukicoder.me/problems/no/1414
にあります.以下に拡張問題を再掲します:
拡張問題
を与えられた整数とする。 以上 以下の整数から,相異なる 個の整数を選ぶ。
選んだ数の集合を とし, に関する以下の条件を考える。
条件: は連続する 個の整数からなる集合を少なくとも つ含む。
(以下同様の記述)
条件を満たすような選び方は何通りあるか。この選び方の数を で割った余りを解答ファイルに出力せよ。
さて,想定解は動画にある通り同様に包除原理で で解けるわけですが,先ほどの手による解法と同様にやると都合が悪いです (悪いのではないかとぼくは思いました).というのも,「 個の場所のうち左から 番目を先頭として連続で が並んでいるような整数解の集合」を考えてしまうと,独立でない集合が出てきてしまって,対称性が失われ厄介です.そこで,捉え方を変えます.evima さんの動画に倣って 個の相異なる整数を選ぶことを, 個の場所があって 個を黒く, 個を白く塗ることと言い換えます.
ここで,さらに, 個の白い場所を並べておいて,その (両端を含む) 個の間隙に合計 個の黒い場所を挿入するととらえ直します. 個のうち,左から 番目の黒い連結成分が 個以上であるような黒い箇所の挿入の仕方 (整数の選び方) の集合を とします.このように数え上げる集合を考えれば,互いに独立であるため対称性から線形時間に落ちます.包除原理は集合の個数が増えても同様に成り立ちます (詳しくは
https://mathtrain.jp/hojo
参照).そこで, を計算してみましょう. は の範囲で動くものとします. 個を 個の中からあらかじめ除いておいて, 個を自由に 箇所に分配すればよく,これは, 個 があって, 個しきりがあり,それらの組み合わせなので, 通りです.これは のみに依存し, には依存しないので,添え字の選び方 通りを選ばれた添え字の数ごとにまとめて で計算することができます.すなわち組み合わせ をかければよく,答えは
を (素数) で計算すればよいです.ただし, の範囲外においては組み合わせは 0 と定義します.素数の剰余環 は体となり逆元は Fermat の小定理で計算可能なのでその上での組みあわせの計算も容易に計算可能です (これは競技プログラミングではよくやる話です.詳しくは
https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
参照).
終わりに
evima さんの動画は簡潔すぎて,(競技プログラミングをさぼっていた自分には特に) 行間を埋めるだけで学びが多いです.連結成分を一つにつぶす,挿入を考えるというのは (玄人にとっては自明なんでしょうが) それをやるだけの問題が AtCoder 難易度 青 diff (結構難しい) に分類されていた気がするので,特殊な訓練を受けていないと一般人には無理だと思います.
evima さんの動画はいつもすばらしく,陰ながら応援しております.この記事が動画を楽しむ一助となれば幸いです.evima ラボ,皆さんチャンネル登録しましょう.
問題の掲載等何か問題があればご一報ください.