#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,638 ms / 2,000 ms
コード長	16,668 bytes
コンパイル時間	239 ms
コンパイル使用メモリ	82,704 KB
実行使用メモリ	268,336 KB
最終ジャッジ日時	2024-06-01 13:58:41
合計ジャッジ時間	31,704 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	160 ms 90,956 KB
testcase_01	AC	163 ms 91,128 KB
testcase_02	AC	162 ms 91,292 KB
testcase_03	AC	158 ms 91,224 KB
testcase_04	AC	159 ms 91,260 KB
testcase_05	AC	1,635 ms 264,256 KB
testcase_06	AC	1,560 ms 266,412 KB
testcase_07	AC	158 ms 91,240 KB
testcase_08	AC	1,078 ms 204,476 KB
testcase_09	AC	1,222 ms 259,332 KB
testcase_10	AC	1,524 ms 265,184 KB
testcase_11	AC	1,638 ms 264,308 KB
testcase_12	AC	159 ms 91,000 KB
testcase_13	AC	466 ms 98,756 KB
testcase_14	AC	1,303 ms 244,880 KB
testcase_15	AC	638 ms 114,948 KB
testcase_16	AC	1,177 ms 268,336 KB
testcase_17	AC	160 ms 90,828 KB
testcase_18	AC	257 ms 94,056 KB
testcase_19	AC	1,140 ms 266,160 KB
testcase_20	AC	809 ms 220,236 KB
testcase_21	AC	675 ms 177,716 KB
testcase_22	AC	1,155 ms 268,332 KB
testcase_23	AC	157 ms 91,088 KB
testcase_24	AC	211 ms 93,044 KB
testcase_25	AC	727 ms 192,916 KB
testcase_26	AC	1,174 ms 268,064 KB
testcase_27	AC	155 ms 90,960 KB
testcase_28	AC	960 ms 261,256 KB
testcase_29	AC	368 ms 108,928 KB
testcase_30	AC	1,076 ms 216,920 KB
testcase_31	AC	611 ms 127,636 KB
testcase_32	AC	429 ms 99,488 KB
testcase_33	AC	461 ms 105,464 KB
testcase_34	AC	471 ms 102,180 KB
testcase_35	AC	829 ms 169,656 KB
testcase_36	AC	524 ms 107,328 KB
testcase_37	AC	785 ms 156,676 KB
testcase_38	AC	464 ms 102,560 KB
testcase_39	AC	943 ms 182,460 KB
testcase_40	AC	806 ms 165,268 KB
testcase_41	AC	877 ms 178,808 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

結果

テストケース

ソースコード