結果
問題 | No.3036 Nauclhlt型文字列 |
ユーザー |
|
提出日時 | 2025-02-28 21:25:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 322 ms / 2,000 ms |
コード長 | 22,536 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 82,244 KB |
実行使用メモリ | 88,848 KB |
最終ジャッジ日時 | 2025-02-28 21:26:00 |
合計ジャッジ時間 | 2,417 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
r"""______________________< it's hidehico's code >----------------------\\.--.|o_o ||:_/ |// \ \(| | )/'\_ _/`\\___)=(___/"""# ライブラリと関数と便利変数# ライブラリimport bisectimport copyimport heapqimport mathimport sysfrom collections import Counter, defaultdict, dequefrom itertools import accumulate, combinations, permutationsfrom math import gcd, lcm, pifrom operator import itemgetterfrom typing import Any, List, Tuple# from atcoder.segtree import SegTree# from atcoder.lazysegtree import LazySegTree# from atcoder.dsu import DSU# cortedcontainersは使うときだけ wandbox非対応なので# from sortedcontainers import SortedDict, SortedSet, SortedList# import pypyjit# pypyjit.set_param("max_unroll_recursion=-1")sys.setrecursionlimit(5 * 10**5)from typing import List# 数学型関数def is_prime(n: int) -> int:"""素数判定します計算量は定数時間です。正確には、繰り返し二乗法の計算量によりですアルゴリズムはミラーラビンの素数判定を使用していますnが2^64を越えると動作しません"""if n == 1:return Falsedef f(a, t, n):x = pow(a, t, n)nt = n - 1while t != nt and x != 1 and x != nt:x = pow(x, 2, n)t <<= 1return t & 1 or x == ntif n == 2:return Trueelif n % 2 == 0:return Falsed = n - 1d >>= 1while d & 1 == 0:d >>= 1checklist = ([2, 7, 61] if 2**32 > n else [2, 325, 9375, 28178, 450775, 9780504, 1795265022])for i in checklist:if i >= n:breakif not f(i, d, n):return Falsereturn Truedef eratosthenes(n: int) -> List[int]:"""n以下の素数を列挙します計算量は、O(n log log n)です先程の素数判定法で列挙するよりも、少し速いです列挙した素数は昇順に並んでいますアルゴリズムはエラトステネスです"""primes = [True] * (n + 1)primes[0], primes[1] = False, Falsei = 2while i**2 <= n:if primes[i]:for k in range(i * 2, n + 1, i):primes[k] = Falsei += 1return [i for i, p in enumerate(primes) if p]def calc_divisors(n: int):"""Nの約数列挙します計算量は、√Nです約数は昇順に並んでいます"""result = []for i in range(1, n + 1):if i * i > n:breakif n % i != 0:continueresult.append(i)if n // i != i:result.append(n // i)return sorted(result)def factorization(n: int) -> List[List[int]]:"""nを素因数分解します計算量は、√Nです(要改善)複数回素因数分解を行なう場合は、√N以下の素数を列挙したので試し割りした法が速いです"""result = []tmp = nfor i in range(2, int(-(-(n**0.5) // 1)) + 1):if tmp % i == 0:cnt = 0while tmp % i == 0:cnt += 1tmp //= iresult.append([i, cnt])if tmp != 1:result.append([tmp, 1])if result == []:result.append([n, 1])return resultdef factorization_plural(L: List[int]) -> List[List[List[int]]]:"""複数の数の素因数分解を行ないます計算量は、O(N * (√max(L) log log √max(L)))みたいな感じです最初に素数を列挙するため、普通の素因数分解より効率がいいです"""res = []primes = eratosthenes(int(max(L) ** 0.5) + 20)def solve(n):t = []for p in primes:if n % p == 0:cnt = 0while n % p == 0:cnt += 1n //= pt.append([p, cnt])if n != 1:t.append([n, 1])if t == []:t.append([n, 1])return tfor n in L:res.append(solve(n))return resdef simple_sigma(n: int) -> int:"""1からnまでの総和を求める関数つまり和の公式"""return (n * (n + 1)) // 2def comb(n: int, r: int, mod: int | None = None) -> int:"""高速なはずの二項係数modを指定すれば、mod付きになる"""a = 1for i in range(n - r + 1, n + 1):a *= iif mod:a %= modb = 1for i in range(1, r + 1):b *= iif mod:b %= modif mod:return a * pow(b, -1, mod) % modelse:return a * b# 多次元配列作成from typing import Any, Listdef create_array1(n: int, default: Any = 0) -> List[Any]:"""1次元配列を初期化する関数"""return [default] * ndef create_array2(a: int, b: int, default: Any = 0) -> List[List[Any]]:"""2次元配列を初期化する関数"""return [[default] * b for _ in [0] * a]def create_array3(a: int, b: int, c: int, default: Any = 0) -> List[List[List[Any]]]:"""3次元配列を初期化する関数"""return [[[default] * c for _ in [0] * b] for _ in [0] * a]from typing import Callabledef binary_search(fn: Callable[[int], bool], right: int = 0, left: int = -1, return_left: bool = True) -> int:"""二分探索の抽象的なライブラリ評価関数の結果に応じて、二分探索する最終的にはleftを出力します関数のテンプレートdef check(mid:int):if A[mid] > x:return Trueelse:return Falsemidは必須です。それ以外はご自由にどうぞ"""while right - left > 1:mid = (left + right) // 2if fn(mid):left = midelse:right = midreturn left if return_left else rightdef mod_add(a: int, b: int, mod: int):"""足し算してmodを取った値を出力O(1)"""return (a + b) % moddef mod_sub(a: int, b: int, mod: int):"""引き算してmodを取った値を出力O(1)"""return (a - b) % moddef mod_mul(a: int, b: int, mod: int):"""掛け算してmodを取った値を出力O(1)"""return (a * b) % moddef mod_div(a: int, b: int, mod: int):"""割り算してmodを取った値を出力フェルマーの小定理を使って計算しますO(log mod)"""return (a * pow(b, mod - 2, mod)) % modclass ModInt:def __init__(self, x: int, mod: int = 998244353) -> None:self.x = x % modself.mod = moddef val(self):return self.xdef rhs(self, rhs) -> int:return rhs.x if isinstance(rhs, ModInt) else rhsdef __add__(self, rhs) -> int:return mod_add(self.x, self.rhs(rhs), self.mod)def __iadd__(self, rhs) -> "ModInt":self.x = self.__add__(rhs)return selfdef __sub__(self, rhs) -> int:return mod_sub(self.x, self.rhs(rhs), self.mod)def __isub__(self, rhs) -> "ModInt":self.x = self.__sub__(rhs)return selfdef __mul__(self, rhs):return mod_mul(self.x, self.rhs(rhs), self.mod)def __imul__(self, rhs):self.x = self.__mul__(rhs)return selfdef __truediv__(self, rhs):return mod_div(self.x, self.rhs(rhs), self.mod)def __itruediv__(self, rhs):self.x = self.__truediv__(rhs)return selfdef __floordiv__(self, rhs):return (self.x // self.rhs(rhs)) % self.moddef __ifloordiv__(self, rhs):self.x = self.__floordiv__(rhs)return selfdef __pow__(self, rhs):return pow(self.x, self.rhs(rhs), self.mod)def __eq__(self, rhs) -> bool:return self.rhs(rhs) == self.xdef __ne__(self, rhs) -> bool:return self.rhs(rhs) != self.x# 標準入力関数import sysfrom typing import Any, Listdef s() -> str:"""一行に一つのstringをinput"""return sys.stdin.readline().rstrip()def sl() -> List[str]:"""一行に複数のstringをinput"""return s().split()def ii() -> int:"""一つのint"""return int(s())def il(add_num: int = 0) -> List[int]:"""一行に複数のint"""return list(map(lambda i: int(i) + add_num, sl()))def li(n: int, func, *args) -> List[List[Any]]:"""複数行の入力をサポート"""return [func(*args) for _ in [0] * n]# YesNo関数def YesNoTemplate(state: bool, upper: bool = False) -> str:"""stateがTrueなら、upperに応じてYes,YESをreturnstateがFalseなら、upperに応じてNo,NOをreturnする"""YES = ["Yes", "YES"]NO = ["No", "NO"]if state:return YES[int(upper)]else:return NO[int(upper)]def YN(state: bool, upper: bool = False) -> None:"""先程のYesNoTemplate関数の結果を出力する"""res = YesNoTemplate(state, upper)print(res)def YE(state: bool, upper: bool = False) -> bool | None:"""boolがTrueならYesを出力してexit"""if not state:return FalseYN(True, upper)exit()def NE(state: bool, upper: bool = False) -> bool | None:"""boolがTrueならNoを出力してexit"""if not state:return FalseYN(False, upper)exit()def coordinate_check(x: int, y: int, H: int, W: int) -> bool:"""座標がグリッドの範囲内にあるかチェックする関数0-indexedが前提"""return 0 <= x < H and 0 <= y < Wfrom typing import List, Tupledef grid_moves(x: int,y: int,H: int,W: int,moves: List[Tuple[int]] = [(0, 1), (0, -1), (1, 0), (-1, 0)],*check_funcs,) -> List[Tuple[int]]:"""現在の座標から、移動可能な座標をmovesをもとに列挙します。xとyは現在の座標HとWはグリッドのサイズmovesは移動する座標がいくつかを保存するcheck_funcsは、その座標の点が#だとかを自前で実装して判定はこちらでするみたいな感じなおcheck_funcsは引数がxとyだけというのが条件追加の判定関数は、弾く場合は、False それ以外ならTrueで"""res = []for mx, my in moves:nx, ny = x + mx, y + myif not coordinate_check(nx, ny, H, W):continuefor f in check_funcs:if not f(nx, ny):breakelse:res.append((nx, ny))return res# DPのテンプレートfrom typing import Listdef partial_sum_dp(lis: List[int], X: int) -> List[bool]:"""部分和dpのテンプレートlisは品物ですdp配列の長さは、Xにします計算量は、O(X*len(L))みたいな感じ返り値は、dp配列で中身は到達できたかを、示すboolです"""dp = [False] * (X + 1)dp[0] = Truefor a in lis:for k in reversed(range(len(dp))):if not dp[k]:continueif k + a >= len(dp):continuedp[k + a] = Truereturn dpdef knapsack_dp(lis: List[List[int]], W: int) -> List[int]:"""ナップサックdpのテンプレートlisは品物のリスト原則品物は、w,vの形で与えられ、wが重さ、vが価値、となる価値と重さを逆転させたい場合は自分でやってくださいdp配列は、定数倍高速化のため、一次元配列として扱うdp配列の長さは、Wとします"""dp = [-(1 << 63)] * (W + 1)dp[0] = 0for w, v in lis:for k in reversed(range(len(dp))):if w + k >= len(dp):continuedp[w + k] = max(dp[w + k], dp[k] + v)return dpdef article_breakdown(lis: List[List[int]]) -> List[List[int]]:"""個数制限付きナップサックの品物を分解します個数の値が、各品物の一番右にあれば正常に動作します"""res = []for w, v, c in lis:k = 1while c > 0:res.append([w * k, v * k])c -= kk = min(2 * k, c)return res# ac_libraryのメモ"""segtree初期化するときSegtree(op,e,v)opはマージする関数例def op(a,b):return a+beは初期化する値vは配列の長さまたは、初期化する内容"""# グラフ構造# 無向グラフfrom collections import dequefrom typing import List, Tupleclass Graph:"""グラフ構造体"""def __init__(self, N: int, dire: bool = False) -> None:"""Nは頂点数、direは有向グラフかです"""self.N = Nself.dire = direself.grath = [[] for _ in [0] * self.N]self.in_deg = [0] * Ndef new_side(self, a: int, b: int):"""注意 0-indexedが前提aとbを辺で繋ぎます有向グラフなら、aからbだけ、無向グラフなら、aからbと、bからaを繋ぎます"""self.grath[a].append(b)if self.dire:self.in_deg[b] += 1if not self.dire:self.grath[b].append(a)def side_input(self):"""標準入力で、新しい辺を追加します"""a, b = map(lambda x: int(x) - 1, input().split())self.new_side(a, b)def input(self, M: int):"""標準入力で複数行受け取り、各行の内容で辺を繋ぎます"""for _ in [0] * M:self.side_input()def get(self, a: int):"""頂点aの隣接頂点を出力します"""return self.grath[a]def all(self) -> List[List[int]]:"""グラフの隣接リストをすべて出力します"""return self.grathdef topological(self, unique: bool = False) -> List[int]:"""トポロジカルソートします有向グラフ限定です引数のuniqueは、トポロジカルソート結果が、一意に定まらないとエラーを吐きます閉路がある、または、uniqueがTrueで一意に定まらなかった時は、[-1]を返します"""if not self.dire:raise ValueError("グラフが有向グラフでは有りません (╥﹏╥)")in_deg = self.in_deg[:]S: deque[int] = deque([])order: List[int] = []for i in range(self.N):if in_deg[i] == 0:S.append(i)while S:if unique and len(S) != 1:return [-1]cur = S.pop()order.append(cur)for nxt in self.get(cur):in_deg[nxt] -= 1if in_deg[nxt] == 0:S.append(nxt)if sum(in_deg) > 0:return [-1]else:return [x for x in order]class GraphW:"""重み付きグラフ"""def __init__(self, N: int, dire: bool = False) -> None:self.N = Nself.dire = direself.grath = [[] for _ in [0] * self.N]def new_side(self, a: int, b: int, w: int):"""注意 0-indexedが前提aとbを辺で繋ぎます有向グラフなら、aからbだけ、無向グラフなら、aからbと、bからaを繋ぎます"""self.grath[a].append((b, w))if not self.dire:self.grath[b].append((a, w))def side_input(self):"""標準入力で、新しい辺を追加します"""a, b, w = map(lambda x: int(x) - 1, input().split())self.new_side(a, b, w + 1)def input(self, M: int):"""標準入力で複数行受け取り、各行の内容で辺を繋ぎます"""for _ in [0] * M:self.side_input()def get(self, a: int) -> List[Tuple[int]]:"""頂点aの隣接頂点を出力します"""return self.grath[a]def all(self) -> List[List[Tuple[int]]]:"""グラフの隣接リストをすべて出力します"""return self.grathfrom collections import defaultdictfrom typing import List# UnionFind木class UnionFind:"""rollbackをデフォルトで装備済み計算量は、経路圧縮を行わないため、基本的なUnionFindの動作は、一回あたり、O(log N)rollbackは、一回あたり、O(1)で行える。"""def __init__(self, n: int) -> None:self.size = nself.data = [-1] * nself.hist = []def root(self, vtx: int) -> int:"""頂点vtxの親を出力します"""if self.data[vtx] < 0:return vtxreturn self.root(self.data[vtx])def same(self, a: int, b: int):"""aとbが連結しているかどうか判定します"""return self.root(a) == self.root(b)def unite(self, a: int, b: int) -> bool:"""aとbを結合しますrootが同じでも、履歴には追加します"""ra, rb = self.root(a), self.root(b)# 履歴を作成するnew_hist = [ra, rb, self.data[ra], self.data[rb]]self.hist.append(new_hist)if ra == rb:return Falseif self.data[ra] > self.data[rb]:ra, rb = rb, raself.data[ra] += self.data[rb]self.data[rb] = rareturn Truedef rollback(self):"""undoしますredoはありません"""if not self.hist:return Falsera, rb, da, db = self.hist.pop()self.data[ra] = daself.data[rb] = dbreturn Truedef all(self) -> List[List[int]]:D = defaultdict(list)for i in range(self.size):D[self.root(i)].append(i)res = []for l in D.values():res.append(l)return res# Trie木class Trie:class Data:def __init__(self, value, ind):self.count = 1self.value = valueself.childs = {}self.ind = inddef __init__(self):self.data = [self.Data("ab", 0)] # 初期値はabにして被らないようにするdef add(self, value: str) -> int:cur = 0result = 0# 再帰的に探索するfor t in value:childs = self.data[cur].childs # 参照渡しでif t in childs:self.data[childs[t]].count += 1else:nd = self.Data(t, len(self.data))childs[t] = len(self.data)self.data.append(nd)result += self.data[childs[t]].count - 1cur = childs[t]return resultdef lcp_max(self, value: str) -> int:cur = 0result = 0for t in value:childs = self.data[cur].childsif t not in childs:breakif self.data[childs[t]].count == 1:breakcur = childs[t]result += 1return resultdef lcp_sum(self, value: str) -> int:cur = 0result = 0for t in value:childs = self.data[cur].childsif t not in childs:breakif self.data[childs[t]].count == 1:breakcur = childs[t]result += self.data[childs[t]].count - 1return resultfrom typing import Listclass BIT:"""BITです要素更新と、区間和を求める事ができます1-indexedです計算量は、一回の動作につきすべてO(log n)です"""def __init__(self, n: int) -> None:self.n: int = nself.bit: List[int] = [0] * (n + 1)def sum(self, i: int) -> int:"""i番目までの和を求めます計算量は、O(log n)です"""res = 0while i:res += self.bit[i]i -= -i & ireturn resdef interval_sum(self, l: int, r: int) -> int:"""lからrまでの総和を求められますlは0-indexedで、rは1-indexedにしてください"""return self.sum(r) - self.sum(l)def add(self, i: int, x: int):"""i番目の要素にxを足します計算量は、O(log n)です"""if i == 0:raise IndexError("このデータ構造は、1-indexedです")while i <= self.n:self.bit[i] += xi += -i & ifrom typing import Tupledef euclid_dis(x1: int, y1: int, x2: int, y2: int) -> int:"""ユークリッド距離を計算します注意:この関数はsqrtを取りません(主に少数誤差用)sqrtを取りたい場合は、自分で計算してください"""return ((x1 - x2) ** 2) + ((y1 - y2) ** 2)def manhattan_dis(x1: int, y1: int, x2: int, y2: int) -> int:"""マンハッタン距離を計算します"""return abs(x1 - x2) + abs(y1 - y2)def manhattan_45turn(x: int, y: int) -> Tuple[int]:"""座標を45度回転します回転すると、マンハッタン距離が、チェビシェフ距離になるので、距離の最大値などが簡単に求められます"""res_x = x - yres_y = x + yreturn res_x, res_ydef chebyshev_dis(x1: int, y1: int, x2: int, y2: int) -> int:"""チェビシェフ距離を計算します"""return max(abs(x1 - x2), abs(y1 - y2))# 便利変数INF = 1 << 63lowerlist = list("abcdefghijklmnopqrstuvwxyz")upperlist = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")# コードN = ii()S = s()NE(N % 2 != 0)YN(True)A = ""B = ""turn = 0for s in S:if turn == 0:A += selse:B += sturn ^= 1print(A, B)