結果
問題 |
No.290 1010
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:45:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 401 ms / 5,000 ms |
コード長 | 2,600 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 108,004 KB |
最終ジャッジ日時 | 2025-03-20 18:45:40 |
合計ジャッジ時間 | 2,279 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
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()