結果
問題 | No.1455 拡張ROTN |
ユーザー |
|
提出日時 | 2021-09-20 12:54:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 4,858 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 70,784 KB |
最終ジャッジ日時 | 2024-07-02 13:37:53 |
合計ジャッジ時間 | 2,512 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#!/usr/bin/env python3import sysdef main():def smallConvert(s: str):return ord(s) - ord("a")def largeConvert(s: str):return ord(s) - ord("A") + 26def decode(i: int):if i < 26:return chr(i + ord("a"))else:return chr(i + ord("A") - 26)class Doubling:""" 初期化処理。Parameters:----------stateKind : int状態の数。dvテーブルの横の長さ。maxDoublingTimes : intダブリングの回数。dvテーブルの縦の長さ。useSum : bool和のダブリングを使用するモードの選択。Returns:----------None"""def __init__(self, stateKind: int, maxDoublingTimes: int, useSum: bool = False):self.dv = [] # 数列(状態)のダブリングテーブル。dv[k][s] := 状態sを2^k回実行したらあとの状態self.sum = [] # 和のダブリングテーブルself.stateKind = stateKind # 状態の種類数sself.maxDoublingTimes = maxDoublingTimes # 実行回数kの範囲の定義(2^0 ≦ k ≦ 2^maxDoublingTimes)# --- Initialize -------------------# STEP.1 テーブルの初期化 2^0(=1)回操作後の状態を生成。self._initTable()# STEP.2 テーブルの更新。if useSum:self._createTableWithSum()else:self._createTable()# ---------------------------------# 初期化処理# 初期化処理は問題毎に記述する。def _initTable(self):l = []for i in range(smallConvert("a"), smallConvert("z")):l.append(i + 1)l.append(smallConvert("a")) # zfor i in range(largeConvert("A"), largeConvert("Z")):l.append(i + 1)l.append(largeConvert("A")) # Zself.dv.append(l)return# ダブリング実施(和を含まない)def _createTable(self):for i in range(1, self.maxDoublingTimes):l = []for j in range(self.stateKind):l.append(self.dv[i - 1][self.dv[i - 1][j]])self.dv.append(l)# ダブリング実施(和を含む)def _createTableWithSum(self):for i in range(1, self.maxDoublingTimes):l = []s = []for j in range(self.stateKind):l.append(self.dv[i - 1][self.dv[i - 1][j]])s.append(self.sum[i - 1][j] + self.sum[i - 1][self.dv[i - 1][j]])self.dv.append(l)self.sum.append(s)""" 指定回数操作後の状態を算出する。Parameters:----------doubingTimes : int求める状態に至る操作回数。startState : int開始する状態。Returns:----------int求めるべく状態"""def getState(self, doubingTimes: int, startState: int):a = []for i in range(self.maxDoublingTimes):if doubingTimes >> i & 1:a.append(i)now = startStatefor i in a:now = self.dv[i][now]return now""""""def getSum(self, doubingTimes: int, startState: int):res = 0a = []for i in range(self.maxDoublingTimes):if doubingTimes >> i & 1:a.append(i)now = startStatefor i in a:res += self.sum[i][now]now = self.dv[i][now]return resdef getAllStates(self, targenTime: int):return self.dv[targenTime]S = list(input())N = int(input())import mathd = Doubling(stateKind=52, maxDoublingTimes=int(math.log2(N)) + 1, useSum=False)ans = []for ss in S:if ss.isdigit():rest = int(ss) + N - 9if rest <= 0:ans.append(str(int(ss) + N))else:for ch in "CpCzNkSuTbEoA":sss = smallConvert(ch) if ch.islower() else largeConvert(ch)ans.append(decode(d.getState(doubingTimes=rest - 1, startState=sss)))else:sss = smallConvert(ss) if ss.islower() else largeConvert(ss)ans.append(decode(d.getState(doubingTimes=N, startState=sss)))print(*ans, sep="")returnif __name__ == '__main__':main()