結果

問題 No.2204 Palindrome Splitting (No Rearrangement ver.)
ユーザー meruuu61779999meruuu61779999
提出日時 2023-02-05 23:45:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,584 ms / 2,000 ms
コード長 4,762 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 156,552 KB
最終ジャッジ日時 2024-07-04 08:58:32
合計ジャッジ時間 31,551 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
55,868 KB
testcase_01 AC 43 ms
55,588 KB
testcase_02 AC 44 ms
56,176 KB
testcase_03 AC 545 ms
78,368 KB
testcase_04 AC 195 ms
77,604 KB
testcase_05 AC 160 ms
77,580 KB
testcase_06 AC 1,237 ms
78,556 KB
testcase_07 AC 824 ms
78,352 KB
testcase_08 AC 661 ms
78,596 KB
testcase_09 AC 865 ms
78,156 KB
testcase_10 AC 1,401 ms
78,352 KB
testcase_11 AC 874 ms
78,268 KB
testcase_12 AC 1,073 ms
78,308 KB
testcase_13 AC 1,581 ms
78,424 KB
testcase_14 AC 648 ms
78,296 KB
testcase_15 AC 1,006 ms
78,552 KB
testcase_16 AC 561 ms
78,084 KB
testcase_17 AC 505 ms
78,640 KB
testcase_18 AC 674 ms
78,180 KB
testcase_19 AC 1,199 ms
78,360 KB
testcase_20 AC 1,584 ms
78,432 KB
testcase_21 AC 1,020 ms
78,588 KB
testcase_22 AC 992 ms
78,176 KB
testcase_23 AC 949 ms
78,292 KB
testcase_24 AC 996 ms
78,288 KB
testcase_25 AC 741 ms
78,376 KB
testcase_26 AC 1,039 ms
78,308 KB
testcase_27 AC 550 ms
78,228 KB
testcase_28 AC 1,021 ms
78,436 KB
testcase_29 AC 923 ms
78,428 KB
testcase_30 AC 43 ms
55,340 KB
testcase_31 AC 44 ms
55,240 KB
testcase_32 AC 961 ms
156,316 KB
testcase_33 AC 1,118 ms
78,408 KB
testcase_34 AC 42 ms
55,352 KB
testcase_35 AC 861 ms
156,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random

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

文字列にハッシュをかけて1次元の数に置き換えます。
長い文字列でも、一致判定をO(1)くらいでできます。

・使い方
rh=RollingHash(S): インスタンス作成。 計算量: O(len(S))
rh.value(l,r): 半開区間[l,r)のハッシュ値を返します。 計算量: O(1)
rh.merged_string_value(section_list):
    半開区間をたくさん入れたリストsection_listについて、
    各区間の文字列を連結させてできる文字列のハッシュ値を返します。
    計算量: O(len(section_list)) (そんなにやばくない)
rh.same(section_list1,section_list2):
    2つの文字列が同じならTrueを、そうでないならFalseを返します。
    計算量: O(len(section_list1)+len(section_list2)) (そんなにやばくない)

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


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


# 区間[left,right)内の素数を1つランダムに出力します。
def prime_generator(left, right):
    while True:
        ret_prime = random.randrange(left, right)
        if is_prime(ret_prime):
            return ret_prime


class RollingHashConst:
    hash_dic = dict()
    rhMOD = prime_generator(1 << 32, 1 << 33)
    cf = random.randrange(1 << 22, 1 << 23)
    rui_cf2 = [1]

    def regist_element(self, el):
        rd = random.randrange(1 << 22, 1 << 23)
        self.hash_dic[el] = rd

    def hashed_value(self, el):
        if el not in self.hash_dic:
            self.regist_element(el)
        return self.hash_dic[el]

    def get_rui_cf(self, length):
        if len(self.rui_cf2) < length:
            self.make_rui_cf(length)
        return self.rui_cf2

    def make_rui_cf(self, length):
        need_add_cnt = length - len(self.rui_cf2)
        for _ in range(need_add_cnt):
            new_val = self.rui_cf2[-1] * self.cf % self.rhMOD
            self.rui_cf2.append(new_val)


class RollingHash(RollingHashConst):
    def __init__(self, init_S):
        self.n = len(init_S)
        self.hashed_list = [0]
        val = 0
        for s in init_S:
            val *= self.cf
            val += self.hashed_value(s)
            val %= self.rhMOD
            self.hashed_list.append(val)

        self.rui_cf = self.get_rui_cf(length=self.n + 1)

    def value(self, l, r):
        assert 0 <= l < r <= self.n, f'0<=l<r<=n, {l=}, {r=}'
        retval = self.hashed_list[r]
        retval -= self.hashed_list[l] * self.rui_cf[r - l] % self.rhMOD
        retval %= self.rhMOD
        return retval

    def merged_string_value(self, section_list):
        value_length_list = []
        for l, r in section_list:
            value_length_list.append((self.value(l, r), r - l))
        right_string_length = 0
        retval = 0
        while value_length_list:
            val, length = value_length_list.pop()
            val *= self.rui_cf[right_string_length]
            val %= self.rhMOD
            right_string_length += length
            retval += val
            retval %= self.rhMOD
        return retval

    def section_length(self, section_list):
        ret_length = 0
        for l, r in section_list:
            ret_length += r - l
        return ret_length

    def same(self, section_list1, section_list2):
        if self.section_length(section_list1) != self.section_length(
                section_list2):
            return False
        if self.merged_string_value(section_list1) != self.merged_string_value(
                section_list2):
            return False
        return True


def main():
    S = input()

    N = len(S)
    S_rev = S[::-1]
    rh = RollingHash(S)
    rh_rev = RollingHash(S_rev)

    def is_palindrome(l, r):
        return rh.value(l, r) == rh_rev.value(N - r, N - l)

    G = [[] for _ in range(N + 1)]
    for i in range(N):
        for j in range(i + 1, N + 1):
            if is_palindrome(i, j):
                G[i].append(j)

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


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