結果

問題 No.2204 Palindrome Splitting (No Rearrangement ver.)
コンテスト
ユーザー meruuu61779999
提出日時 2023-02-03 22:08:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,294 bytes
コンパイル時間 283 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 248,192 KB
最終ジャッジ日時 2024-07-02 20:06:28
合計ジャッジ時間 3,970 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

inputs = sys.stdin.readline

"""ローリングハッシュ

・使い方
rh=RollingHash(S: str): 初期状態
rh.addright(s): 右側に文字sをつけ加えます。
rh.addleft(s):  左側に文字sをつけ加えます。
rh.eraseright(): 右側の文字を削除します。空ならNoneを返します。
rh.eraseleft():  左側の文字を削除します。空ならNoneを返します。
rh.change(after_s,idx): idx番目(0-indexed)の文字を削除して、その場所に別の文字を挿入します。
A==B: 2つの文字列が同じかどうかを判定します(O(1)だよ)

・使わせてもらったもの
ミラーラビン素数判定法【https://qiita.com/srtk86/items/609737d50c9ef5f5dc59】
"""

import random
from collections import deque


def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True


class const:
    max_length = 5005
    cf = random.randint(1 << 59, 1 << 60)
    mod = random.randint(1 << 63, 1 << 64)
    while not is_prime(mod):
        mod = random.randint(1 << 63, 1 << 64)
    cf_div = pow(cf, mod - 2, mod)

    # hash_dic[(英文字)] = 乱数
    hash_dic = dict()
    for i in range(26):
        hash_dic[chr(97 + i)] = random.randint(2, 1 << 60)  # 英小文字
        hash_dic[chr(65 + i)] = random.randint(2, 1 << 60)  # 英大文字

    # rui_cf[i]: cf^i を mod で割ったあまり
    rui_cf = [1]
    tail = 1
    for _ in range(max_length):
        tail = tail * cf % mod
        rui_cf.append(tail)


class RollingHash(const):
    def __init__(self, s=""):
        self.length = len(s)
        self.value = 0
        for i, el in enumerate(s):
            self.value += self.rui_cf[self.length - 1 - i] * self.hash_dic[
                el] % self.mod
            self.value %= self.mod
        self.que = deque(s)

    def __len__(self):
        return self.length

    def __eq__(self, other):
        value_ok = (self.value == other.value)
        len_ok = (len(self) == len(other))
        return value_ok and len_ok

    def addright(self, s1):
        self.value *= self.cf
        self.value += self.hash_dic[s1]
        self.value %= self.mod
        self.que.append(s1)
        self.length += 1

    def addleft(self, s1):
        self.value += self.rui_cf[self.length] * self.hash_dic[s1] % self.mod
        self.value %= self.mod
        self.que.appendleft(s1)
        self.length += 1

    def eraseright(self):
        if self.length == 0:
            return None
        s1 = self.que.pop()
        self.value -= self.hash_dic[s1]
        self.value *= self.cf_div
        self.value %= self.mod
        self.length -= 1
        return True

    def eraseleft(self):
        if self.length == 0:
            return None
        s1 = self.que.popleft()
        self.value -= self.hash_dic[s1]
        self.value *= self.cf_div
        self.value %= self.mod
        self.length -= 1
        return True

    def change(self, after_s, idx):
        if self.length <= idx:
            return None
        erase_s = self.que[idx]
        self.value -= self.rui_cf[self.length - idx - 1] * self.hash_dic[
            erase_s]
        self.value += self.rui_cf[self.length - idx - 1] * self.hash_dic[
            after_s]
        self.value %= self.mod
        return True


def main():
    S = input()
    G = [[] for _ in range(len(S))]
    for i in range(len(S)):
        rh = RollingHash()
        rh_rev = RollingHash()
        for j in range(i, len(S)):
            rh.addright(S[j])
            rh_rev.addleft(S[j])
            if rh == rh_rev:
                G[i].append(j)

    score = [0] * (len(S) + 1)
    score[0] = 1 << 30
    for i in range(len(S)):
        now_score = score[i]
        for ni in G[i]:
            length = ni - i + 1
            new_score = min(length, now_score)
            score[ni + 1] = max(score[ni + 1], new_score)
    print(score[-1])
    # print(score)


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