鳩の巣原理とは？アルゴリズム検定問題の具体例を使って解説

Aru

競技プログラミングの問題でよく利用されている原理に「鳩の巣原理」があります。鳩の巣原理とはなんでしょうか。この記事では、鳩の巣原理についてわかりやすく解説します。また、アルゴリズム実技検定の問題を例に、鳩の巣原理の使い方を解説したいと思います。

Contents

鳩の巣原理
問題を解く
まとめ

鳩の巣原理

鳩の巣原理とは、「n羽の鳩がm個の箱に入っている場合、鳩の数が箱より多い、つまりn>mであれば少なくとも１つの箱に１羽より多い鳩が入っている」というものです。ｍ個の箱に、それよりも多いn羽の鳩が入っているんだから、当然同じ箱に入っている鳩が必ず存在します。

例えば、２つの箱にボールを３個入れる場合、ボールの入れ方は０：３、１：２、２：１、３：０個の４種類になります。どの入れ方でも、どちらかの箱には１個より多いボールが入ることになります。

これをどのように使うというと、一定の規則性で箱に入れる場合、m個入れるところまで計算しておいてあとは周期性を利用するという感じです。

ちょっとわかりにくいので具体例で説明します。

例えば、$a_x = 10x + 1$で生成される数列を3で割った余りを求める場合を考えます。3で割った余りは同然ですが0/1/2のいずれかの値になります。なので、$a_x(mod 3)$は、0/1/2の値のいずれかになり、規則的に10ずつ加算させていく数列なので0/1/2が繰り返されます（周期性を持ちます）。

実際に計算してみると$a_x = 10x + 1$で生成される数列を3で割った余りは、1→2→0を繰り返します（下図）。

このように、等差数列をpで割った余りは周期性を持ちます。この周期性を利用すれば、１周期だけ計算しておけば、数列のn番目の値を素早く計算することが可能です。

具体的にn番目の値を計算する場合は、繰り返しの部分を無視して最後のn%3がいくつかだけ見ることで解答することができます。

下図は具体的な計算方法ですが、1→2→0を繰り返している部分は無視できるので、3で割った余り（n%3）の部分だけ遷移をチェックすれば良いことになります。

第12回アルゴリズム実技検定 I問題は、この原理を利用して解く問題になります。

問題を解く

問題概要（PAST12のI問題）

この問題、設問の意図がわかりにくいですが、よく読むと以下を答えれば良いことに気づきます。

毎日A円ずつ高くなっていくリンゴをM円の商品券を使って購入する場合に、無駄になる金額の総和は？

例えば、１００円の商品券で３０円のものを購入する場合、おつりがもらえないのであれば７０円の損（無駄）になります。

商品は、１日目３０円、２日目６０円と値段が上がっていきます。なので、無駄も７０円、４０円と変化していきます。

鳩の巣原理をどこで使うか？

シミュレーションすると気づくと思いますが、無駄なお金はM円未満になります。

この問題では、M≦300と小さいのでM+1回計算すれば、必ず同じ余りになることがわかります（周期性があります）。

ここが鳩の巣原理です。M個の箱にM+1個のものを入れようとすると必ず１つの箱は１つより多くなります。

ということで、最大M回目まで計算しておけば、あとは同じパターンの繰り返しになります。

同じ値が現れるまで繰り返す

以下、同じ値が現れるまでシミュレーションする部分です。aには累積和を入れておきます。

変数aは、最初0が入っている状態にしています。これは、a[-1]+eの計算でエラーが起きないようにするためです。

また、変数mで、値が出現したことがあるかどうかを管理しています。もし、出現した場合は、そこでループを抜けます（if m[e]: breakの部分）。

    a = [0]
    m = [False] * M
    tot = 0
    while True :
        tot += A
        e = (M-tot%M)%M
        if m[e] : break
        m[e] = True
        a.append(a[-1]+e)

計算結果を使って求める

先ほどのループを抜けた状態で、１つのループの合計値がリストaの末尾に、i個目までの累積和がa[i]に格納された状態になっています。

まず、サイクルが何回入っているかを計算します（N//(len(a)-1)）。次に、あまりの部分を計算します。

繰り返し回数xと、余りyを計算したら、答えを計算します。

    x, y = N//(len(a)-1), N%(len(a)-1)

    ans = x*a[-1] + a[y]

全体のプログラム

以下、問題を解くプログラム全体です（Python）。

t = int(input())

for _ in range(t) :
    N, A, M = map(int, input().split())

    a = [0]
    m = [False] * M
    tot = 0
    while True :
        tot += A
        e = (M-tot%M)%M
        if m[e] : break
        m[e] = True
        a.append(a[-1]+e)
    
    x, y = N//(len(a)-1), N%(len(a)-1)

    ans = x*a[-1] + a[y]

    print(ans)

まとめ

mで割った余りは、m個以上のパターンが出現することはないので鳩の巣原理を使って、繰り返しパターンまでを計算しておき、あとは、計算した１サイクル分のデータを使って計算するという手法が使えます。AtCoderのABC問題にも、このような方法で解ける問題が結構あります。鳩の巣原理は覚えておくと良いと思います。

#AtCoder #python #鳩の巣原理