ABC200D - Happy Birthday! 2

解法1：鳩の巣原理＋bit全探索

考え方

200で割った余りは200通りだけであるから，201個調べれば必ず同じものがある．$2^{N} > 200$となる最小の$N$は$8$なので，先頭の$8$個を全探索すれば十分．

アライグマ「D問題は、鳩の巣原理なのだ！　201個以上の組み合わせを試せば、200で割ったあまりが同じになる組み合わせは絶対見つかるから、先頭8つだけを使う2^8パターンを全探索すればいいのだ！」
フェネック「第1回最強コン本戦Aが類題だねー」https://t.co/3KBTMkkieT

— 競技プログラミングをするフレンズ (@kyopro_friends) May 8, 2021

回答例

N = int(input())
A = list(map(lambda x:int(x) % 200, input().split()))

def print_ans(bit):
    ans = []
    for i in range(num):
        if bit >> i & 1:
            ans.append(i + 1)
    print(len(ans), *ans)

num = min(N, 8)
A = A[:num]
memo = [-1] * 200
for bit in range(1 << num):
    cumsum = 0
    for i in range(num):
        if bit >> i & 1:
            cumsum += A[i]
            cumsum %= 200
    if memo[cumsum] > 0:
        print('Yes')
        print_ans(memo[cumsum])
        print_ans(bit)
        exit()
    memo[cumsum] = bit

print('No')

解法2：DP＋経路復元

考え方

回答例