結果

問題 No.2204 Palindrome Splitting (No Rearrangement ver.)
ユーザー meruuu61779999meruuu61779999
提出日時 2023-02-05 23:45:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,830 ms / 2,000 ms
コード長 4,762 bytes
コンパイル時間 474 ms
コンパイル使用メモリ 86,896 KB
実行使用メモリ 157,924 KB
最終ジャッジ日時 2023-09-17 13:26:45
合計ジャッジ時間 39,173 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
72,036 KB
testcase_01 AC 92 ms
72,276 KB
testcase_02 AC 93 ms
72,080 KB
testcase_03 AC 775 ms
78,912 KB
testcase_04 AC 335 ms
78,756 KB
testcase_05 AC 263 ms
78,744 KB
testcase_06 AC 1,492 ms
79,084 KB
testcase_07 AC 1,298 ms
79,204 KB
testcase_08 AC 1,282 ms
79,364 KB
testcase_09 AC 1,327 ms
79,688 KB
testcase_10 AC 1,005 ms
79,304 KB
testcase_11 AC 955 ms
79,580 KB
testcase_12 AC 705 ms
79,764 KB
testcase_13 AC 1,363 ms
79,320 KB
testcase_14 AC 1,435 ms
79,164 KB
testcase_15 AC 780 ms
79,928 KB
testcase_16 AC 367 ms
78,836 KB
testcase_17 AC 477 ms
79,840 KB
testcase_18 AC 907 ms
79,496 KB
testcase_19 AC 894 ms
79,588 KB
testcase_20 AC 897 ms
79,580 KB
testcase_21 AC 1,447 ms
79,340 KB
testcase_22 AC 963 ms
79,228 KB
testcase_23 AC 1,376 ms
79,568 KB
testcase_24 AC 1,232 ms
79,892 KB
testcase_25 AC 1,352 ms
79,540 KB
testcase_26 AC 1,457 ms
79,872 KB
testcase_27 AC 1,083 ms
79,688 KB
testcase_28 AC 1,116 ms
79,436 KB
testcase_29 AC 1,476 ms
79,304 KB
testcase_30 AC 95 ms
71,828 KB
testcase_31 AC 92 ms
71,908 KB
testcase_32 AC 1,069 ms
157,924 KB
testcase_33 AC 1,830 ms
79,400 KB
testcase_34 AC 92 ms
71,912 KB
testcase_35 AC 968 ms
157,796 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