ABC242Eを解いた【回文】

筆者はレート800前後の茶～緑コーダ

ABC242のE問題を解いていく

実装コード

公式解説の抜粋

A=0,B=1,...Z=25と見立てた26進法を考える。

上位N//2文字が何番目か、それより前の回文はカウントするので確定、また、そしてその文字の後ろを回文に揃えたとき、元の文字より前か後ろかでカウントするかどうかが変わる。

main.py

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

class ModInt:
    def __init__(self, x, mod = 998244353):
        self.mod = mod
        self.x = x.x if isinstance(x, ModInt) else x % self.mod
    __str__ = lambda self:str(self.x)
    __repr__ = __str__
    __int__ = lambda self: self.x
    __index__ = __int__
    __add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
    __sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
    __mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
    __pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, self.mod))
    __truediv__ = lambda self, other: ModInt(self.x * pow(ModInt(other).x, self.mod - 2, self.mod))
    __floordiv__ = lambda self, other: ModInt(self.x // ModInt(other).x)
    __lt__ = lambda self, other: self.x < ModInt(other).x
    __gt__ = lambda self, other: self.x > ModInt(other).x
    __le__ = lambda self, other: self.x <= ModInt(other).x
    __ge__ = lambda self, other: self.x >= ModInt(other).x
    __eq__ = lambda self, other: self.x == ModInt(other).x
    __ne__ = lambda self, other: self.x!= ModInt(other).x

class mint(ModInt):
    pass

A2Z = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
d = {s:i for i,s in enumerate(A2Z)}

def main():
    T = rI()
    
    for _ in range(T):
        N = rI()
        S = rS()
        
        ans = mint(0)
        for i in range((N-1)//2+1):
            ans*=26
            ans+=d[S[i]]
            err(S[i],d[S[i]],ans)
        T = list(S)
        l,r=0,N-1
        while l<r:
            T[r]=T[l]
            l+=1
            r-=1
        # err("".join(T),S,"".join(T) <= S)
        if "".join(T) <= S:
            ans+=1
        print(ans)
    # print('Yes' if ans else 'No')
    
if __name__ == '__main__':
    main()

まとめ

ABC242のE問題を解いた。

今回のポイントは、アルファベットを26進数に見立てる点だと実装しているうちに感じた。そのような発想が出るような地力を今後もつけていきたい。