結果

問題 No.3036 Nauclhlt型文字列
ユーザー hidehic0
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

r"""
 ______________________
< it's hidehico's code >
 ----------------------
   \
    \
        .--.
       |o_o |
       |:_/ |
      //   \ \
     (|     | )
    /'\_   _/`\
    \___)=(___/
"""
# ライブラリと関数と便利変数
# ライブラリ
import bisect
import copy
import heapq
import math
import sys
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from math import gcd, lcm, pi
from operator import itemgetter
from 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 False
    def f(a, t, n):
        x = pow(a, t, n)
        nt = n - 1
        while t != nt and x != 1 and x != nt:
            x = pow(x, 2, n)
            t <<= 1
        return t & 1 or x == nt
    if n == 2:
        return True
    elif n % 2 == 0:
        return False
    d = n - 1
    d >>= 1
    while d & 1 == 0:
        d >>= 1
    checklist = (
        [2, 7, 61] if 2**32 > n else [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    )
    for i in checklist:
        if i >= n:
            break
        if not f(i, d, n):
            return False
    return True
def eratosthenes(n: int) -> List[int]:
    """
    n以下の素数を列挙します
    計算量は、O(n log log n)です
    先程の素数判定法で列挙するよりも、少し速いです
    列挙した素数は昇順に並んでいます
    アルゴリズムはエラトステネスです
    """
    primes = [True] * (n + 1)
    primes[0], primes[1] = False, False
    i = 2
    while i**2 <= n:
        if primes[i]:
            for k in range(i * 2, n + 1, i):
                primes[k] = False
        i += 1
    return [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:
            break
        if n % i != 0:
            continue
        result.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 = n
    for i in range(2, int(-(-(n**0.5) // 1)) + 1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            result.append([i, cnt])
    if tmp != 1:
        result.append([tmp, 1])
    if result == []:
        result.append([n, 1])
    return result
def 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 = 0
                while n % p == 0:
                    cnt += 1
                    n //= p
                t.append([p, cnt])
        if n != 1:
            t.append([n, 1])
        if t == []:
            t.append([n, 1])
        return t
    for n in L:
        res.append(solve(n))
    return res
def simple_sigma(n: int) -> int:
    """
    1からnまでの総和を求める関数
    つまり和の公式
    """
    return (n * (n + 1)) // 2
def comb(n: int, r: int, mod: int | None = None) -> int:
    """
    高速なはずの二項係数
    modを指定すれば、mod付きになる
    """
    a = 1
    for i in range(n - r + 1, n + 1):
        a *= i
        if mod:
            a %= mod
    b = 1
    for i in range(1, r + 1):
        b *= i
        if mod:
            b %= mod
    if mod:
        return a * pow(b, -1, mod) % mod
    else:
        return a * b
# 多次元配列作成
from typing import Any, List
def create_array1(n: int, default: Any = 0) -> List[Any]:
    """
    1次元配列を初期化する関数
    """
    return [default] * n
def 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 Callable
def 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 True
        else:
            return False
    midは必須です。それ以外はご自由にどうぞ
    """
    while right - left > 1:
        mid = (left + right) // 2
        if fn(mid):
            left = mid
        else:
            right = mid
    return left if return_left else right
def mod_add(a: int, b: int, mod: int):
    """
    足し算してmodを取った値を出力
    O(1)
    """
    return (a + b) % mod
def mod_sub(a: int, b: int, mod: int):
    """
    引き算してmodを取った値を出力
    O(1)
    """
    return (a - b) % mod
def mod_mul(a: int, b: int, mod: int):
    """
    掛け算してmodを取った値を出力
    O(1)
    """
    return (a * b) % mod
def mod_div(a: int, b: int, mod: int):
    """
    割り算してmodを取った値を出力
    フェルマーの小定理を使って計算します
    O(log mod)
    """
    return (a * pow(b, mod - 2, mod)) % mod
class ModInt:
    def __init__(self, x: int, mod: int = 998244353) -> None:
        self.x = x % mod
        self.mod = mod
    def val(self):
        return self.x
    def rhs(self, rhs) -> int:
        return rhs.x if isinstance(rhs, ModInt) else rhs
    def __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 self
    def __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 self
    def __mul__(self, rhs):
        return mod_mul(self.x, self.rhs(rhs), self.mod)
    def __imul__(self, rhs):
        self.x = self.__mul__(rhs)
        return self
    def __truediv__(self, rhs):
        return mod_div(self.x, self.rhs(rhs), self.mod)
    def __itruediv__(self, rhs):
        self.x = self.__truediv__(rhs)
        return self
    def __floordiv__(self, rhs):
        return (self.x // self.rhs(rhs)) % self.mod
    def __ifloordiv__(self, rhs):
        self.x = self.__floordiv__(rhs)
        return self
    def __pow__(self, rhs):
        return pow(self.x, self.rhs(rhs), self.mod)
    def __eq__(self, rhs) -> bool:
        return self.rhs(rhs) == self.x
    def __ne__(self, rhs) -> bool:
        return self.rhs(rhs) != self.x
# 標準入力関数
import sys
from typing import Any, List
def 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をreturn
    stateが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 False
    YN(True, upper)
    exit()
def NE(state: bool, upper: bool = False) -> bool | None:
    """
    boolがTrueならNoを出力してexit
    """
    if not state:
        return False
    YN(False, upper)
    exit()
def coordinate_check(x: int, y: int, H: int, W: int) -> bool:
    """
    座標がグリッドの範囲内にあるかチェックする関数
    0-indexedが前提
    """
    return 0 <= x < H and 0 <= y < W
from typing import List, Tuple
def 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 + my
        if not coordinate_check(nx, ny, H, W):
            continue
        for f in check_funcs:
            if not f(nx, ny):
                break
        else:
            res.append((nx, ny))
    return res
# DPのテンプレート
from typing import List
def 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] = True
    for a in lis:
        for k in reversed(range(len(dp))):
            if not dp[k]:
                continue
            if k + a >= len(dp):
                continue
            dp[k + a] = True
    return dp
def 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] = 0
    for w, v in lis:
        for k in reversed(range(len(dp))):
            if w + k >= len(dp):
                continue
            dp[w + k] = max(dp[w + k], dp[k] + v)
    return dp
def article_breakdown(lis: List[List[int]]) -> List[List[int]]:
    """
    個数制限付きナップサックの品物を分解します
    個数の値が、各品物の一番右にあれば正常に動作します
    """
    res = []
    for w, v, c in lis:
        k = 1
        while c > 0:
            res.append([w * k, v * k])
            c -= k
            k = min(2 * k, c)
    return res
# ac_libraryのメモ
"""
segtree
初期化するとき
Segtree(op,e,v)
opはマージする関数
例
def op(a,b):
    return a+b
eは初期化する値
vは配列の長さまたは、初期化する内容
"""
# グラフ構造
# 無向グラフ
from collections import deque
from typing import List, Tuple
class Graph:
    """
    グラフ構造体
    """
    def __init__(self, N: int, dire: bool = False) -> None:
        """
        Nは頂点数、direは有向グラフかです
        """
        self.N = N
        self.dire = dire
        self.grath = [[] for _ in [0] * self.N]
        self.in_deg = [0] * N
    def 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] += 1
        if 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.grath
    def 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] -= 1
                if 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 = N
        self.dire = dire
        self.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.grath
from collections import defaultdict
from typing import List
# UnionFind木
class UnionFind:
    """
    rollbackをデフォルトで装備済み
    計算量は、経路圧縮を行わないため、基本的なUnionFindの動作は、一回あたり、O(log N)
    rollbackは、一回あたり、O(1)で行える。
    """
    def __init__(self, n: int) -> None:
        self.size = n
        self.data = [-1] * n
        self.hist = []
    def root(self, vtx: int) -> int:
        """
        頂点vtxの親を出力します
        """
        if self.data[vtx] < 0:
            return vtx
        return 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 False
        if self.data[ra] > self.data[rb]:
            ra, rb = rb, ra
        self.data[ra] += self.data[rb]
        self.data[rb] = ra
        return True
    def rollback(self):
        """
        undoします
        redoはありません
        """
        if not self.hist:
            return False
        ra, rb, da, db = self.hist.pop()
        self.data[ra] = da
        self.data[rb] = db
        return True
    def 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 = 1
            self.value = value
            self.childs = {}
            self.ind = ind
    def __init__(self):
        self.data = [self.Data("ab", 0)]  # 初期値はabにして被らないようにする
    def add(self, value: str) -> int:
        cur = 0
        result = 0
        # 再帰的に探索する
        for t in value:
            childs = self.data[cur].childs  # 参照渡しで
            if t in childs:
                self.data[childs[t]].count += 1
            else:
                nd = self.Data(t, len(self.data))
                childs[t] = len(self.data)
                self.data.append(nd)
            result += self.data[childs[t]].count - 1
            cur = childs[t]
        return result
    def lcp_max(self, value: str) -> int:
        cur = 0
        result = 0
        for t in value:
            childs = self.data[cur].childs
            if t not in childs:
                break
            if self.data[childs[t]].count == 1:
                break
            cur = childs[t]
            result += 1
        return result
    def lcp_sum(self, value: str) -> int:
        cur = 0
        result = 0
        for t in value:
            childs = self.data[cur].childs
            if t not in childs:
                break
            if self.data[childs[t]].count == 1:
                break
            cur = childs[t]
            result += self.data[childs[t]].count - 1
        return result
from typing import List
class BIT:
    """
    BITです
    要素更新と、区間和を求める事ができます
    1-indexedです
    計算量は、一回の動作につきすべてO(log n)です
    """
    def __init__(self, n: int) -> None:
        self.n: int = n
        self.bit: List[int] = [0] * (n + 1)
    def sum(self, i: int) -> int:
        """
        i番目までの和を求めます
        計算量は、O(log n)です
        """
        res = 0
        while i:
            res += self.bit[i]
            i -= -i & i
        return res
    def 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] += x
            i += -i & i
from typing import Tuple
def 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 - y
    res_y = x + y
    return res_x, res_y
def chebyshev_dis(x1: int, y1: int, x2: int, y2: int) -> int:
    """
    チェビシェフ距離を計算します
    """
    return max(abs(x1 - x2), abs(y1 - y2))
# 便利変数
INF = 1 << 63
lowerlist = list("abcdefghijklmnopqrstuvwxyz")
upperlist = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# コード
N = ii()
S = s()
NE(N % 2 != 0)
YN(True)
A = ""
B = ""
turn = 0
for s in S:
    if turn == 0:
        A += s
    else:
        B += s
    turn ^= 1
print(A, B)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0