pigeonhole principle

date: 2021-05-08 excerpt: pigeonhole principle(鳩の巣原理)について

tag: algorithm math 鳩の巣原理 pigeonhole principle

pigeonhole principle(鳩の巣原理)について

m > nのとき、nの箱にm個の要素を当てはめると必ず一つは2個以上になる
当たり前のことであると思うが、実際に適応例がすぐ出てこなかったりする

参考

鳩の巣原理

例; 鳩の巣の原理を使うことで計算量を大幅に限定できる例

問題
京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200); D - Happy Birthday! 2

解説
200で割ったあまりが等しいということなので、0 < n <= 200までで示される組み合わせが２つ以上存在するか、と読み替えられる
読み替えることができると、bit全探索に持ち込むことができる

回答

N=int(input())
A=list(map(int,input().split()))

cnt = min(8, len(A))

bk=[[] for i in range(200)]

for i in range(1, 1<<cnt): # 最大8bit表現から
    sig = 0
    s = []
    for j in range(0, cnt):
        if i&(1<<j) != 0: # つまりbitが共起したら
            s.append(j+1)
            sig+=A[j]
            sig%=200

    if len(bk[sig]) != 0:
        print("Yes")
        print(len(bk[sig]), *bk[sig])
        print(len(s), *s)
        exit()
    else:
        bk[sig] = s

print("No")