halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ABC150F - Xor Shift

競プロ 今日の精進 ABC 黄Diff

毎日格上の問題を倒すやつの33日目です。

問題リンク

atcoder.jp

問題概要

「数列 a を x 回シフトしてから一様に y をxorしたら b に一致する」ような (x,y) の組をすべて求めてね。

解法

いつものbitごとに考えるあれです。

各bitごとにみると、シフトはローリングハッシュみたいなことをすればできます。

一様にxorして一致するかは、元のものと反転バージョンを両方用意して一致判定すればいいです。

ハッシュの衝突だけ注意…*1

提出コード

from random import randint
MOD=pow(2,61)-1
BASE=randint(3,MOD)
N=int(input())
fin=pow(BASE,N-1,MOD)
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=[0]*N
for i in range(30):
    hash_a=0
    hash_rv=0
    hash_b=0
    for j in range(N):
        hash_a*=BASE
        hash_b*=BASE
        hash_rv*=BASE
        hash_a+=(a[j]>>i)&1
        hash_b+=(b[j]>>i)&1
        hash_rv+=((a[j]>>i)&1)^1
        hash_a%=MOD
        hash_b%=MOD
        hash_rv%=MOD
    for j in range(N):
        if hash_b==hash_rv:
            ans[j]+=1<<i
        elif hash_b!=hash_a:
            ans[j]=-1
        hash_a-=fin*((a[j]>>i)&1)
        hash_rv-=fin*(((a[j]>>i)&1)^1)
        hash_a*=BASE
        hash_rv*=BASE
        hash_a+=(a[j]>>i)&1
        hash_rv+=((a[j]>>i)&1)^1
        hash_a%=MOD
        hash_rv%=MOD
for j in range(N):
    if ans[j]!=-1:
        print(j,ans[j])

Submission #46868012 - AtCoder Beginner Contest 150

感想

精選150問で見たやつ、今見ると瞬殺できて楽しい

空いてた日にやってたこと

24日目

25日目

26日目

27日目

28日目

29日目

30日目

31日目

32日目

*1:別の問題だけどひっかかりまくった