結果

問題 No.2226 Hello, Forgotten World!
ユーザー ygd.ygd.
提出日時 2023-02-24 22:15:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,889 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 81,936 KB
実行使用メモリ 265,568 KB
最終ジャッジ日時 2024-09-13 05:37:19
合計ジャッジ時間 3,737 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
81,600 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
#input = sys.stdin.readline
#input = sys.stdin.buffer.readline #文字列はダメ
#sys.setrecursionlimit(1000000)
import math
import bisect
#import itertools
#import random
#from heapq import heapify, heappop, heappush
from collections import defaultdict
from collections import deque
import copy #DeepCopy: hoge = [_[:] for _ in hogehoge]
#from functools import lru_cache
#@lru_cache(maxsize=None)
#MOD = pow(10,9) + 7
MOD = 998244353
dx = [1,0,-1,0]
dy = [0,1,0,-1]
#dx8 = [1,1,0,-1,-1,-1,0,1]
#dy8 = [0,1,1,1,0,-1,-1,-1]

base1 = 1007; base2 = 2009
mod1 = 1000000007; mod2 = 1000000009

class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r): #S[l:r]indexでいうl文字目からr-1文字目。r-l文字。
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

def get_hash(s,base,mod):
    ns = len(s)
    ret = 0
    v = 0
    for i in range(ns):
        v = (v * base + ord(s[i])) % mod
        ret += v
        ret %= mod
    return ret


def main():
    word = "helloworld"
    ok1 = set([]); ok2 = set([])
    n = len(word)
    for i in range(1<<n):
        temp = ""
        for j in range(n):
            if (i>>j)&1 == 1:
                temp += '?'
            else:
                temp += word[j]
        RH1 = RollingHash(temp,base1,mod1)
        RH2 = RollingHash(temp,base2,mod2)
        ok1.add(RH1.get(0,10))
        ok2.add(RH2.get(0,10))
        # if i == 0:
        #     print(temp)
        #     print(RH1.get(0,10))
    
    T = int(input())
    for _ in range(T):
        N = int(input())
        S = input()
        RH1 = RollingHash(S,base1,mod1)
        RH2 = RollingHash(S,base2,mod2)
        ans = []
        # print(RH1.get(0,0+10))
        last = []
        for i in range(N-9):
            if RH1.get(i,i+10) in ok1 and  RH2.get(i,i+10) in ok2:
                last.append(i)
        if len(last) == 0:
            print(-1)
            continue
        L = []
        for l in last:
            idx = 0
            while idx < N:
                if idx != l:
                    if S[idx] == '?':
                        ans.append('a')
                    else:
                        ans.append(S[idx])
                    idx += 1
                else:
                    ans.append("helloworld")
                    idx += 10
            t = "".join(ans)
            # print(t)
            if len(L) == 0:
                L.append("".join(ans))
            else:
                if L[0] > t:
                    L[0] = t
        print(L[0])
                        

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