鳩の巣原理と、競技プログラミングでの使われ方を紹介します。鳩の巣原理とは昔々あるところに、5羽の鳩がおりました。彼らをすべて巣箱に入れたいのですが、あいにく巣は4つしかありませんでした。すると以下の図のように、どこか1つの巣には2羽以上の鳩が入ってしまいます。適当な入れ方をすると、2羽より多い巣があったり、空の巣があるかもしれません。どんな入れ方をしても「どこかの巣には2羽以上」入ることが保証されます。つの巣には鳩が2羽以上入ります。巣に入っている鳩の最大数を最小化しようとすると、各巣になるべく均等に鳩を配る形になります。なり、これが最大値の下限になります。した例で、最低でも3羽以上の鳩が入っている巣があることを示しています。鳩の巣原理自体は一見当たり前に思えますが、「鳩」と「巣」をなにと捉えるかで様々な応用が効きます。準備運動として、鳩の巣原理を応用した事例をいくつか示して使い方をなんとなく眺めてみることにしましょう。<1の位>任意の11個の整数の中に、1の位が等しい数のペアが存在する。11個の整数を「鳩」、1の位に出現する10種類の数「0」「1」「2」・・・「9」を巣と考える。すると、鳩の巣原理により少なくとも2つの整数(鳩)が、同じ1の位の数(巣)に分類される。任意の2頂点以上の無向単純グラフに、次数の等しい頂点のペアが存在する。(他のすべての頂点と繋がっている)頂点があるかないかで場合分けする。頂点は同じ次数を持つ。頂点は同じ次数を持つ。任意の部分集合には、一方がもう片方を割り切るようなペアが存在する。50}を適切に分割すると、以下の性質を満たす互いに素な部分集合を25個作れることを示す。【部分集合に含まれる任意の異なる2数を選んだとき、一方が他方を割り切る】1以上50以下の奇数はちょうど25個ある。それらを別々の集合に分ける。偶数は2で割れるだけ割ると奇数になり、割る前の偶数たちをその奇数と同じ集合に入れる。...といった形の25個の集合が得られる。それぞれの集合が性質を満たすことは明らかである。以上より、鳩は26羽、巣は25個となる。2つの数が同じ集合に属する。一方が片方を割り切ることが言える。なんとなく使い方のイメージは掴めたでしょうか。ある問題で「鳩の巣原理が使えるかも?」と思ったら、「巣」と、それより多い「鳩」が何かをそれぞれ考えることで、「同じグループに属するペア」の存在を容易に示すことができるかもしれません。競技プログラミングにおける鳩の巣原理ここまでは数学の話でした。競技プログラミングで鳩の巣原理が使われる問題のパターンを幾つか紹介します。「指定された条件を満たす解を一つ」出す問題で、解の存在を保証するために使われることがあります。典型ですが、次の問題について考えてみましょう。倍数にできるだろうか。できる場合、その部分列を具体的に答えよ。できない場合、その旨を報告せよ。割ったあまりを「鳩」「巣」と考えれば、必ず余りの数が等しい、異なる部分和がありますね!よって、答えは必ず存在します。倍数になるので、それを出力すればよいです。解法に直接役立ちはしないものの、探索の範囲を限定できる証明に使われることがあります。RectangleAvoidingColoring】のグリッドセルの幾つかのマス目が白か黒で塗られている。残りのマス目を白か黒で塗りたい。その時、以下の条件を満たすようにする。塗り方は何通りあるだろうか。以上の大きさの場合は、必ず4隅が等しい長方形が存在することが示せます。すると、短い方の長さが4以下の場合だけを考えればよいので、bitDPなどで数え上げができます。大きさ5x5のグリッドの先頭の行に着目する。鳩の巣原理より、そのうちの少なくとも3色は同じ色になる。一般性を失わず、その色を白とできる。(黒が3色以上あったとすると、白黒を反転させれば以下同文になる)先頭の色が白の列を3つピックアップする。先頭以外の4行について、行に含まれる白の数の最大数で場合分けする。白の数が2つ以上の行があるとき該当する2列を抜き出せば、4隅が白の四角形ができる。ある場合は、残りの3行と組み合わせて4隅が黒の四角形ができる。含む行がない場合は、鳩の巣原理によりパターンが等しい行のペアがあり、4隅が黒の四角形ができる。最後に、鳩の巣原理を使って解ける面白い問題を発見したので紹介します。「鳩」と「巣」が何になるかが難しいので、まだ解いてない人は是非考えてみてください。editorialは出ていますが、後日解説を書きます。