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

提出ソース

結果

問題	No.2073 Concon Substrings (Swap Version)
ユーザー	McGregorsh
提出日時	2022-09-16 23:03:44
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,640 ms / 2,000 ms
コード長	16,668 bytes
コンパイル時間	302 ms
コンパイル使用メモリ	87,224 KB
実行使用メモリ	268,748 KB
最終ジャッジ日時	2023-08-23 16:31:49
合計ジャッジ時間	34,303 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	243 ms 86,256 KB
testcase_01	AC	245 ms 86,448 KB
testcase_02	AC	243 ms 86,256 KB
testcase_03	AC	240 ms 86,208 KB
testcase_04	AC	242 ms 86,232 KB
testcase_05	AC	1,619 ms 266,124 KB
testcase_06	AC	1,547 ms 265,744 KB
testcase_07	AC	245 ms 86,308 KB
testcase_08	AC	1,121 ms 198,028 KB
testcase_09	AC	1,258 ms 250,308 KB
testcase_10	AC	1,545 ms 263,036 KB
testcase_11	AC	1,640 ms 264,284 KB
testcase_12	AC	238 ms 86,288 KB
testcase_13	AC	531 ms 95,040 KB
testcase_14	AC	1,352 ms 243,556 KB
testcase_15	AC	725 ms 110,232 KB
testcase_16	AC	1,191 ms 268,368 KB
testcase_17	AC	243 ms 86,264 KB
testcase_18	AC	343 ms 89,984 KB
testcase_19	AC	1,146 ms 267,160 KB
testcase_20	AC	855 ms 207,484 KB
testcase_21	AC	738 ms 170,712 KB
testcase_22	AC	1,180 ms 268,596 KB
testcase_23	AC	244 ms 86,456 KB
testcase_24	AC	304 ms 89,220 KB
testcase_25	AC	796 ms 188,904 KB
testcase_26	AC	1,200 ms 268,748 KB
testcase_27	AC	242 ms 86,252 KB
testcase_28	AC	970 ms 247,476 KB
testcase_29	AC	437 ms 104,672 KB
testcase_30	AC	1,093 ms 220,016 KB
testcase_31	AC	665 ms 124,592 KB
testcase_32	AC	503 ms 96,672 KB
testcase_33	AC	538 ms 102,224 KB
testcase_34	AC	539 ms 98,936 KB
testcase_35	AC	876 ms 166,928 KB
testcase_36	AC	584 ms 105,176 KB
testcase_37	AC	820 ms 155,596 KB
testcase_38	AC	529 ms 98,532 KB
testcase_39	AC	976 ms 180,400 KB
testcase_40	AC	836 ms 159,808 KB
testcase_41	AC	911 ms 174,296 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

結果

テストケース

ソースコード