#798371 (PyPy3) No.2073 Concon Substrings (Swap Version)

提出ソース

結果

問題	No.2073 Concon Substrings (Swap Version)
ユーザー	Panda
提出日時	2022-09-16 23:03:44
言語	PyPy3 (7.3.8)
結果	AC
実行時間	1,703 ms / 2,000 ms
コード長	16,668 bytes
コンパイル時間	301 ms
使用メモリ	272,224 KB
最終ジャッジ日時	2023-01-11 08:22:06
合計ジャッジ時間	35,996 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間使用メモリ
testcase_00	AC	269 ms 91,240 KB
testcase_01	AC	270 ms 91,236 KB
testcase_02	AC	270 ms 91,200 KB
testcase_03	AC	272 ms 91,188 KB
testcase_04	AC	275 ms 91,244 KB
testcase_05	AC	1,638 ms 269,736 KB
testcase_06	AC	1,611 ms 270,276 KB
testcase_07	AC	269 ms 91,204 KB
testcase_08	AC	1,157 ms 206,704 KB
testcase_09	AC	1,296 ms 257,820 KB
testcase_10	AC	1,587 ms 269,032 KB
testcase_11	AC	1,703 ms 266,616 KB
testcase_12	AC	273 ms 91,168 KB
testcase_13	AC	595 ms 99,512 KB
testcase_14	AC	1,368 ms 247,804 KB
testcase_15	AC	766 ms 117,588 KB
testcase_16	AC	1,219 ms 271,524 KB
testcase_17	AC	274 ms 91,208 KB
testcase_18	AC	377 ms 93,732 KB
testcase_19	AC	1,188 ms 271,712 KB
testcase_20	AC	898 ms 212,804 KB
testcase_21	AC	759 ms 173,780 KB
testcase_22	AC	1,222 ms 271,572 KB
testcase_23	AC	273 ms 91,028 KB
testcase_24	AC	331 ms 92,048 KB
testcase_25	AC	813 ms 192,092 KB
testcase_26	AC	1,201 ms 272,224 KB
testcase_27	AC	268 ms 91,172 KB
testcase_28	AC	997 ms 250,988 KB
testcase_29	AC	472 ms 108,820 KB
testcase_30	AC	1,144 ms 220,828 KB
testcase_31	AC	714 ms 124,736 KB
testcase_32	AC	558 ms 100,880 KB
testcase_33	AC	580 ms 105,112 KB
testcase_34	AC	583 ms 103,120 KB
testcase_35	AC	900 ms 168,436 KB
testcase_36	AC	638 ms 107,516 KB
testcase_37	AC	879 ms 160,072 KB
testcase_38	AC	593 ms 102,856 KB
testcase_39	AC	1,020 ms 181,348 KB
testcase_40	AC	885 ms 160,860 KB
testcase_41	AC	970 ms 181,484 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

###順序付き多重集合###

import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')

class SortedMultiset(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 170

    def _build(self, a=None) -> None:
        "Evenly divide `a` into buckets."
        if a is None: a = list(self)
        size = self.size = len(a)
        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
        self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]
    
    def __init__(self, a: Iterable[T] = []) -> None:
        "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
        a = list(a)
        if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
            a = sorted(a)
        self._build(a)

    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i: yield j

    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i): yield j
    
    def __len__(self) -> int:
        return self.size
    
    def __repr__(self) -> str:
        return "SortedMultiset" + str(self.a)
    
    def __str__(self) -> str:
        s = str(list(self))
        return "{" + s[1 : len(s) - 1] + "}"

    def _find_bucket(self, x: T) -> List[T]:
        "Find the bucket which should contain x. self must not be empty."
        for a in self.a:
            if x <= a[-1]: return a
        return a

    def __contains__(self, x: T) -> bool:
        if self.size == 0: return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        return i != len(a) and a[i] == x

    def count(self, x: T) -> int:
        "Count the number of x."
        return self.index_right(x) - self.index(x)

    def add(self, x: T) -> None:
        "Add an element. / O(√N)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return
        a = self._find_bucket(x)
        insort(a, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()

    def discard(self, x: T) -> bool:
        "Remove an element and return True if removed. / O(√N)"
        if self.size == 0: return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i == len(a) or a[i] != x: return False
        a.pop(i)
        self.size -= 1
        if len(a) == 0: self._build()
        return True

    def lt(self, x: T) -> Union[T, None]:
        "Find the largest element < x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x: T) -> Union[T, None]:
        "Find the largest element <= x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x: T) -> Union[T, None]:
        "Find the smallest element > x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x: T) -> Union[T, None]:
        "Find the smallest element >= x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]
    
    def __getitem__(self, x: int) -> T:
        "Return the x-th element, or IndexError if it doesn't exist."
        if x < 0: x += self.size
        if x < 0: raise IndexError
        for a in self.a:
            if x < len(a): return a[x]
            x -= len(a)
        raise IndexError

    def index(self, x: T) -> int:
        "Count the number of elements < x."
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x: T) -> int:
        "Count the number of elements <= x."
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans


###セグメントツリー###

#####segfunc#####
def segfunc(x, y):
    return x + y
    # 最小値　　　　min(x, y)　
    # 最大値　　　　max(x, y)
    # 区間和　　　　x + y
    # 区間積　　　　x * y
    # 最大公約数　　math.gcd(x, y)
    # 排他的論理和　　　　x ^ y
#################

#####ide_ele#####
ide_ele = 0
    # 最小値    float('inf')
    # 最大値　　-float('inf')
    # 区間和　　　　0
    # 区間積　　　　1
    # 最大公約数　　0
    # 排他的論理和　0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


###UnionFind###

from collections import defaultdict

class UnionFind():
    """
    Union Find木クラス

    Attributes
    --------------------
    n : int
        要素数
    root : list
        木の要素数
        0未満であればそのノードが根であり、添字の値が要素数
    rank : list
        木の深さ
    """

    def __init__(self, n):
        """
        Parameters
        ---------------------
        n : int
            要素数
        """
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def find(self, x):
        """
        ノードxの根を見つける

        Parameters
        ---------------------
        x : int
            見つけるノード

        Returns
        ---------------------
        root : int
            根のノード
        """
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        """
        木の併合

        Parameters
        ---------------------
        x : int
            併合したノード
        y : int
            併合したノード
        """
        x = self.find(x)
        y = self.find(y)

        if(x == y):
            return
        elif(self.rank[x] > self.rank[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

    def same(self, x, y):
        """
        同じグループに属するか判定

        Parameters
        ---------------------
        x : int
            判定したノード
        y : int
            判定したノード

        Returns
        ---------------------
        ans : bool
            同じグループに属しているか
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        木のサイズを計算

        Parameters
        ---------------------
        x : int
            計算したい木のノード

        Returns
        ---------------------
        size : int
            木のサイズ
        """
        return -self.root[self.find(x)]

    def roots(self):
        """
        根のノードを取得

        Returns
        ---------------------
        roots : list
            根のノード
        """
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_size(self):
        """
        グループ数を取得

        Returns
        ---------------------
        size : int
            グループ数
        """
        return len(self.roots()) - 1

    def group_members(self):
        """
        全てのグループごとのノードを取得

        Returns
        ---------------------
        group_members : defaultdict
            根をキーとしたノードのリスト
        """
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members


###素因数分解###

def prime_factorize(n: int) -> list:
   return_list = []
   while n % 2 == 0:
   	  return_list.append(2)
   	  n //= 2
   f = 3
   while f * f <= n:
   	  if n % f == 0:
   	  	  return_list.append(f)
   	  	  n //= f
   	  else:
   	  	  f += 2
   if n != 1:
   	  return_list.append(n)
   return return_list


###ある数が素数かどうかの判定###

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True
    

###N以下の素数列挙###

import math 
def sieve_of_eratosthenes(n):
	  prime = [True for i in range(n+1)]
	  prime[0] = False
	  prime[1] = False
	  
	  sqrt_n = math.ceil(math.sqrt(n))
	  for i in range(2, sqrt_n+1):
	  	  if prime[i]:
	  	  	  for j in range(2*i, n+1, i):
	  	  	  	  prime[j] = False
	  return prime


###N以上K以下の素数列挙###

import math

def segment_sieve(a, b):
	  sqrt_b = math.ceil(math.sqrt(b))
	  prime_small = [True for i in range(sqrt_b)]
	  prime = [True for i in range(b-a+1)]
	  
	  for i in range(2, sqrt_b):
	  	  if prime_small[i]:
	  	  	  for j in range(2*i, sqrt_b, i):
	  	  	  	  prime_small[j] = False
	  	  	  for j in range((a+i-1)//i*i, b+1, i):
	  	  	  	  #print('j: ', j)
	  	  	  	  prime[j-a] = False
	  return prime


###n進数から10進数変換###

def base_10(num_n,n):
	  num_10 = 0
	  for s in str(num_n):
	  	  num_10 *= n
	  	  num_10 += int(s)
	  return num_10


###10進数からn進数変換###

def base_n(num_10,n):
	  str_n = ''
	  while num_10:
	  	  if num_10%n>=10:
	  	  	  return -1
	  	  str_n += str(num_10%n)
	  	  num_10 //= n
	  return int(str_n[::-1])


###複数の数の最大公約数、最小公倍数###

from functools import reduce

# 最大公約数
def gcd_list(num_list: list) -> int:
	  return reduce(gcd, num_list)

# 最小公倍数
def lcm_base(x: int, y: int) -> int:
	  return (x * y) // gcd(x, y)
def lcm_list(num_list: list):
	  return reduce(lcm_base, num_list, 1)


###約数列挙###

def make_divisors(n):
	  lower_divisors, upper_divisors = [], []
	  i = 1
	  while i * i <= n:
	  	  if n % i == 0:
	  	  	  lower_divisors.append(i)
	  	  	  if i != n // i:
	  	  	  	  upper_divisors.append(n//i)
	  	  i += 1
	  return lower_divisors + upper_divisors[::-1]


###順列###

def nPr(n, r):
	  npr = 1
	  for i in range(n, n-r, -1):
	  	  npr *= i
	  return npr


###組合せ###

def nCr(n, r):
	  factr = 1
	  r = min(r, n - r)
	  for i in range(r, 1, -1):
	  	  factr *= i
	  return nPr(n, r)/factr


###組合せMOD###

def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk


import sys, re
from fractions import Fraction
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement, permutations
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext, ROUND_HALF_UP
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
def get_distance(x1, y1, x2, y2):
	  d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
	  return d
def rotate(table):
   	  n_fild = []
   	  for x in zip(*table[::-1]):
   	  	  n_fild.append(x)
   	  return n_fild
sys.setrecursionlimit(10 ** 7)
INF = float('inf')
MOD = 10 ** 9 + 7
MOD2 = 998244353


###関数コピーしたか？###
def main():
   
   N = int(input())
   S = input()
   
   S1 = SortedMultiset()
   S2 = SortedMultiset()
   S3 = SortedMultiset()
   
   for i in range(3*N):
   	  if i % 3 == 0:
   	  	  if S[i] == 'c':
   	  	  	  S1.add(1)
   	  	  elif S[i] == 'o':
   	  	  	  S1.add(2)
   	  	  elif S[i] == 'n':
   	  	  	  S1.add(3)
   	  	  else:
   	  	  	  S1.add(0)
   	  if i % 3 == 1:
   	  	  if S[i] == 'c':
   	  	  	  S2.add(1)
   	  	  elif S[i] == 'o':
   	  	  	  S2.add(2)
   	  	  elif S[i] == 'n':
   	  	  	  S2.add(3)
   	  	  else:
   	  	  	  S2.add(0)
   	  if i % 3 == 2:
   	  	  if S[i] == 'c':
   	  	  	  S3.add(1)
   	  	  elif S[i] == 'o':
   	  	  	  S3.add(2)
   	  	  elif S[i] == 'n':
   	  	  	  S3.add(3)
   	  	  else:
   	  	  	  S3.add(0)
   
   ans = 0
   cou = 0
   for i in range(3*N):
   	  if i % 3 == 0:
   	  	  if cou == 0:
   	  	  	  strs = 1
   	  	  	  if strs in S1:
   	  	  	  	  cou = 1
   	  	  	  	  S1.discard(1)
   	  	  	  else:
   	  	  	  	  cou = 0
   	  	  	  	  S1.discard(0)
   	  	  elif cou == 1:
   	  	  	  strs = 2
   	  	  	  if strs in S1:
   	  	  	  	  cou = 2
   	  	  	  	  S1.discard(2)
   	  	  	  else:
   	  	  	  	  cou = 0
   	  	  	  	  S1.discard(0)
   	  	  else:
   	  	  	  strs = 3
   	  	  	  if strs in S1:
   	  	  	  	  cou = 3
   	  	  	  	  S1.discard(3)
   	  	  	  else:
   	  	  	  	  cou = 0
   	  	  	  	  S1.discard(0)
   	  	  
   	  	  if cou == 3:
   	  	  	  ans += 1
   	  	  	  cou = 0
   	  
   	  if i % 3 == 1:
   	  	  if cou == 0:
   	  	  	  strs = 1
   	  	  	  if strs in S2:
   	  	  	  	  cou = 1
   	  	  	  	  S2.discard(1)
   	  	  	  else:
   	  	  	  	  cou = 0
   	  	  	  	  S2.discard(0)
   	  	  elif cou == 1:
   	  	  	  strs = 2
   	  	  	  if strs in S2:
   	  	  	  	  cou = 2
   	  	  	  	  S2.discard(2)
   	  	  	  else:
   	  	  	  	  cou = 0
   	  	  	  	  S2.discard(0)
   	  	  else:
   	  	  	  strs = 3
   	  	  	  if strs in S2:
   	  	  	  	  cou = 3
   	  	  	  	  S2.discard(3)
   	  	  	  else:
   	  	  	  	  cou = 0
   	  	  	  	  S2.discard(0)
   	  	  
   	  	  if cou == 3:
   	  	  	  ans += 1
   	  	  	  cou = 0
   	  
   	  if i % 3 == 2:
   	  	  if cou == 0:
   	  	  	  strs = 1
   	  	  	  if strs in S3:
   	  	  	  	  cou = 1
   	  	  	  	  S3.discard(1)
   	  	  	  else:
   	  	  	  	  cou = 0
   	  	  	  	  S3.discard(0)
   	  	  elif cou == 1:
   	  	  	  strs = 2
   	  	  	  if strs in S3:
   	  	  	  	  cou = 2
   	  	  	  	  S3.discard(2)
   	  	  	  else:
   	  	  	  	  cou = 0
   	  	  	  	  S3.discard(0)
   	  	  else:
   	  	  	  strs = 3
   	  	  	  if strs in S3:
   	  	  	  	  cou = 3
   	  	  	  	  S3.discard(3)
   	  	  	  else:
   	  	  	  	  cou = 0
   	  	  	  	  S3.discard(0)
   	  	  
   	  	  if cou == 3:
   	  	  	  ans += 1
   	  	  	  cou = 0
   print(ans)
   
if __name__ == '__main__':
    main()

yukicoder

結果

テストケース

ソースコード