結果

問題 No.290 1010
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:18:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 393 ms / 5,000 ms
コード長 2,600 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 107,976 KB
最終ジャッジ日時 2025-03-20 20:18:39
合計ジャッジ時間 2,419 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N = int(sys.stdin.readline())
    S = sys.stdin.readline().strip()
    if N < 2:
        print("NO")
        return
    
    # Step 1: Check for adjacent duplicates (L=1)
    for i in range(N - 1):
        if S[i] == S[i+1]:
            print("YES")
            return
    
    if N < 4:
        print("NO")
        return
    
    # Rolling Hash preparation with two different bases and mods
    class RollingHash:
        def __init__(self, s, base, mod):
            self.mod = mod
            self.base = base
            n = len(s)
            self.prefix_hash = [0] * (n + 1)
            self.power = [1] * (n + 1)
            for i in range(n):
                self.prefix_hash[i+1] = (self.prefix_hash[i] * base + ord(s[i])) % mod
                self.power[i+1] = (self.power[i] * base) % mod

        def get_hash(self, l, r):
            # Returns hash of s[l..r) (0-based)
            res = (self.prefix_hash[r] - self.prefix_hash[l] * self.power[r - l]) % self.mod
            return res
    
    # Using two different hashing setups to reduce collision probability
    base1, mod1 = 911382629, 10**18 + 3
    base2, mod2 = 3571428571, 10**18 + 7
    rh1 = RollingHash(S, base1, mod1)
    rh2 = RollingHash(S, base2, mod2)
    
    # Step 2: Check for L from 2 to 20
    for L in range(2, 21):
        max_i = N - 2 * L
        if max_i < 0:
            continue
        for i in range(max_i + 1):
            # Check hash1 for the two parts
            h1_part1 = rh1.get_hash(i, i + L)
            h1_part2 = rh1.get_hash(i + L, i + 2 * L)
            if h1_part1 != h1_part2:
                continue
            # Check hash2 to confirm
            h2_part1 = rh2.get_hash(i, i + L)
            h2_part2 = rh2.get_hash(i + L, i + 2 * L)
            if h2_part1 == h2_part2:
                print("YES")
                return
    
    # Step 3: Check for larger L values
    max_L = N // 2
    start_L = max_L
    end_L = max(max_L - 19, 1)  # Check up to 20 largest possible L values
    for L in range(start_L, end_L - 1, -1):
        max_i_val = N - 2 * L
        if max_i_val < 0:
            continue
        for i in range(max_i_val + 1):
            h1_part1 = rh1.get_hash(i, i + L)
            h1_part2 = rh1.get_hash(i + L, i + 2 * L)
            if h1_part1 != h1_part2:
                continue
            h2_part1 = rh2.get_hash(i, i + L)
            h2_part2 = rh2.get_hash(i + L, i + 2 * L)
            if h2_part1 == h2_part2:
                print("YES")
                return
    
    print("NO")

if __name__ == "__main__":
    main()
0