AtCoder Beginner Contest 200 - D Happy Birthday! 2 を嘘解法した (嘘・エスパーシリーズ Ver.2)

皆さんこんばんは！
炎上記事Part 2 です！！
本日行われたABCで今度は嘘解法してしまいました！！！

ABC200の結果

というか、今回はエスパーのつもりはなくて、とりまなんもすることないし、適当にやって嘘解法でも提出しちゃえ！！！ってやったらACして発狂しました。。。

ちなみに前回のエスパー記事はこちら

ryusuke920.hatenablog.jp

問題はこちら

D - Happy Birthday! 2

要約すると、配列 A からいくつか取り出し、余りが同じになる異なる取り出し方はありますか？という問題です。

今回は前回のように、エスパーの中での自分なりの考えすらもなく、ただ脳死で提出したので何を提出したのかをお話しします。

コード

早速ですが、まずはACしたコードを載せようと思います！こちら！！

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i] %= 200

num = [[] for _ in range(200)]

for i in range(n):
    cnt = a[i]
    cnt %= 200
    num[cnt].append([i + 1])

for i in range(n - 1):
    for j in range(i + 1, n):
        cnt = a[i] + a[j]
        cnt %= 200
        num[cnt].append([i + 1, j + 1])

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            cnt = a[i] + a[j] + a[k]
            cnt %= 200
            num[cnt].append([i + 1, j + 1, k + 1])

for i in range(len(num)):
    if len(num[i]) >= 2:
        print("Yes")
        print(len(num[i][0]), *num[i][0])
        print(len(num[i][1]), *num[i][1])
        exit()
print("No")

最初に言います。
なんでこれでACできるのかわかっていません！！
鳩の巣原理でなんかやるんだろうなーとは速攻で思ったんですけど（これも合っているのか分からんが。）そこからがわからなかった。

あとNが大きい時はどうせ鳩の巣原理で絶対にYesだろうくらいには思いました。

これ、何をしているのかと言うと、時間内に間に合う限りで全探索してみようと言う発想です！
N <= 200 の制約になっていたので、O(N^3) までなら間に合うかと言うことで、

Part 1 すべての始まりO(N)

num = [[] for _ in range(200)]

for i in range(n):
    cnt = a[i]
    cnt %= 200
    num[cnt].append([i + 1])

ここでは、まず O(N) で余りが 200 パターンのうち、何になるかを計算しています。

Part 2 ちょっとレベルアップ O(N^2)

for i in range(n - 1):
    for j in range(i + 1, n):
        cnt = a[i] + a[j]
        cnt %= 200
        num[cnt].append([i + 1, j + 1])

ここでは、２つの組み合わせで作れる余りを全列挙しています。時間も余裕で間に合いますよね。

Part 3 最後のステップ O(N^3)！！！！！

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            cnt = a[i] + a[j] + a[k]
            cnt %= 200
            num[cnt].append([i + 1, j + 1, k + 1])

ここでは、３つの組み合わせで作れる余りを全列挙しています。

答えはYes or No ?

最後にこのnum(上記の余りのパターンを格納した配列)の中身を全探索（200通り）し、あるあまりが２パターン以上(lengthが2以上)あれば、違う組み合わせで余りが同じになるパターンがあると言うことなので、それを出力します。

逆に見つからなかった場合は、一致する余りがないと言うことになる（はず）なので No を出力してACしました。

最後に

なんでこれでACしたのか本当によくわかりません。
緑になってから、エスパーして大幅にレートが上がるか、失敗して下がっているかの２択です。辛いです。

追記（解説見ました 2021/05/08/23:00現在）

Bit全探索？？？
は？？なにそれおいしいの？？？？