鳩の巣原理特集 - 問題解決の宝石箱

Competitive Programming Advent Calendar 2016 23日目の記事です。 鳩の巣原理と、競技プログラミングでの使われ方を紹介します。 鳩の巣原理とは 昔々あるところに、5羽の鳩がおりました。彼らをすべて巣箱に入れたいのですが、あいにく巣は4つしかありませんでした。 すると以下の図のように、どこか1つの巣には2羽以上の鳩が入ってしまいます。 適当な入れ方をすると、2羽より多い巣があったり、空の巣があるかもしれません。でも、どんな入れ方をしても「どこかの巣には2羽以上」入ることが保証されます 。 一般に n 羽の鳩を m < n 個の巣にいれるとき、どこか 1 つの巣には鳩が2羽以上入ります。 更に一般化。巣に入っている鳩の最大数を最小化しようとすると、各巣になるべく均等に鳩を配る形になります。 このとき、鳩の数の最大値は *1 となり、これが最大値の下限

[sh19910711]

"n 羽の鳩を m < n 個の巣にいれるとき、どこか 1 つの巣には鳩が2羽以上入ります / 「鳩」と「巣」をなにと捉えるかで様々な応用が / 競技プログラミングにおける鳩の巣原理: 解の存在保証 + 探索範囲の上限の保証"