AtCoder ABC150 メモ

新ABCで初めてDが解けなかったです。出た回数がそもそもそんなに多くないですが...

D SemiCommonMultiple

タイトルの通り公倍数の半分が回答になりそうで、証明が面倒なのでsubmit → WA 手元で計算すると2で割れる回数が全て同じでないとダメという条件が得られてもう一度submit → TLE しばらく考えていると「Dのテストケースに誤りがあるのでunrated」と告知があったので諦めました。 AC者がいるので解けるはずだとは思いましたが。

終了後、他の方の回答を眺めているとLCMが大きくなりすぎて計算時間が増大していたようです。ある程度大きくなったら回答は0とわかるので打ち切ってAC

E Change a Little Bit

こちらは割と簡単でした。unratedが決まった時点で少し途中退席してしまったのでコンテスト中には解ききれませんでしたが、継続していれば解けていたと思います。 回答は解説PDFと同じだったので省略。

F XOR Shift

考えたけど解けませんでした。 Aiのk bit目を並べたものとBiの k bit目を並べたもののXOR が0か(1<<N - 1)のどちらかになるようにshiftしていけば解けるかと思いましたがTLE for ループの回数はN*30で大丈夫なはずですが、bit演算時に2**(10**5)bitの計算をしないといけないので無理だったようです。 いや、思いついた時から間に合わなさそうだとは思ったのですが、依然かなり大きな数のbit演算でも大丈夫だった経験があったので意外とうまく行くかと。 bit演算の内側がわかっていないので何桁くらいまでだとO(1)とみなしていいのかわかっていないのが問題ですね。 twitterで同様のことを試した方を見つけて手元で試すとNが10**4くらいまでなら通る計算だそうです。ってことは多言語なら通った解法なんでしょうか。

解説を見てAC。KMP法を使いました。 実装は以下の記事にあるものを利用。元記事では一番はじめに見つけた単語位置しか返さない仕様なので少し変更しています。

パターン部分一致の文字列検索 (KMP法) - Qiita

def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1
    while j < len(word):
        matched = word[i] == word[j]
        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i
    return table

def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0
    results = []
    while i < len(text) and p < len(word):
        if text[i] == word[p]:
            i += 1
            p += 1
            if p == len(word):
                p = table[p]
                results.append((i-len(word), i))
        elif p == 0:
            i += 1
        else:
            p = table[p]
    return results

N, = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
A = []
B = []
for i in range(2*N-1):
    A.append(As[i%N] ^ As[(i+1)%N])
    if i < N:
        B.append(Bs[i%N] ^ Bs[(i+1)%N])
for k, l in kmp_search(A, B):
    print(k, As[k] ^ Bs[0])