結果
問題 | No.2073 Concon Substrings (Swap Version) |
ユーザー |
![]() |
提出日時 | 2023-01-10 22:10:15 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 9,649 bytes |
コンパイル時間 | 777 ms |
コンパイル使用メモリ | 13,568 KB |
実行使用メモリ | 18,352 KB |
最終ジャッジ日時 | 2024-12-21 12:23:03 |
合計ジャッジ時間 | 7,934 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 17 WA * 20 |
ソースコード
# ライブラリインポート------------------------------------------import mathimport collections#import statisticsfrom copy import deepcopyfrom collections import defaultdict,dequefrom sys import exit,setrecursionlimitfrom heapq import heapify,heappush,heappopfrom bisect import bisect_left,bisect_right,insortfrom itertools import product,permutations,combinations,accumulate,combinations_with_replacementfrom decimal import Decimal#from numpy import array,matrix,dot,Tfrom functools import lru_cachefrom typing import Generic, Iterable, Iterator, TypeVar, Union, Listfrom string import ascii_uppercase, ascii_lowercase# お決まり------------------------------------------------INF=10**18 # まれに足りない場合もあるMOD=10**9+7mod=998244353def YesNo(b): print("Yes") if b else print("No")def YESNO(b): print("YES") if b else print("NO")dxy4=[(1,0),(-1,0),(0,1),(0,-1)]dxy8=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]ALPHA=ascii_uppercasealpha=ascii_lowercasesetrecursionlimit(2*10**5)def PrintHW(array,hight,width):for i in range(hight): print(*array[i][:width])def sortx(array,num): return sorted(array, key=lambda x:x[num])def sortxr(array,num): return sorted(array, key=lambda x:x[num], reverse=True)def LL(h,w,e=0): return [[e for i in range(w)] for j in range(h)]def LLL(a,b,c,e=0): return [LL(b,c,e) for _ in range(a)]def LLLL(a,b,c,d,e=0): return [LLL(b,c,d,e) for _ in range(a)]def DD(): return defaultdict(int) # 初期値指定ならdefaultdict(lambda: 1)などとするdef LB(n): return [[] for _ in range(n)]def Dc(x): return Decimal(str(x))#@lru_cache(maxsize=2*10**5)# 入力----------------------------------------------------def II(): return int(input())def MI(): return map(int, input().split())def TI(): return tuple(map(int, input().split()))def LI(): return list(MI())def SLI(): return sorted(LI())def MS(): return map(str, input().split())def LS(): return list(MS())def LLI(rows): return [LI() for _ in range(rows)]def LLS(rows): return [list(input()) for _ in range(rows)]def Graph0(vertex,edge,LLI):ret=[[] for _ in range(vertex)]for [u,v] in LLI:u-=1; v-=1; # 消す場合もありret[u].append(v); ret[v].append(u);return retdef Banhei(hight,width,LLS,wall='#'): # 01マップなら0ret=[[wall]*(width+2)]for i in range(hight):ret.append([wall]+LLS[i]+[wall])ret.append([wall]*(width+2))return retdef MLI(n): # [A,B] = MLI(N)のように使うarr=LLI(n); l=len(arr[0])ret=[[] for _ in range(l)]for i in range(n):for j in range(l): ret[j].append(arr[i][j])return retdef ALLI(): # 何個与えられるかわからないときres=[]while True:try: res.append(LI())except: breakreturn res# 出力カンペ--------------------------------------------"""print(''.join(['a', 'b', 'c'])) # abcprint("{:b}".format(b)) # 1100101010 2進数表記print("{:o}".format(b)) # 1452 8進数表記print("{:x}".format(b)) # 32a 16進数小文字表記print("{:X}".format(b)) # 32A 16進数大文字表記print("python".ljust(15,'-')) # 左詰め python---------print("python".center(15,'-'))# 中寄せ -----python----print("python".rjust(15,'-')) # 右詰め ---------pythonprint(str(29).rjust(10,'0')) # 10桁ゼロ埋め 0000000029print("{:.8f}".format(a/b)) # 小数点以下の桁数指定表示N='aiueokakikukeko'N=N.translate(str.maketrans({'a':'A'})) #N = AiueokAkikukeko"""# 頻出ツール------------------------------------------def acc(A):# 配列Aの累積和、最初に0を追加する。return [0] + list(accumulate(A))def acc2d(A,H,W):# サイズH*Wの2次元配列Aの2次元累積和。先頭に0を挿入。B=LL(H+1,W+1)for x in range(H):for y in range(W):B[x+1][y+1]=A[x][y]for x in range(H+1):for y in range(1,W+1):B[x][y] += B[x][y-1]for x in range(1,H+1):for y in range(W+1):B[x][y] += B[x-1][y]return Bdef fac(n, m=0):# nの階乗 | m:mod(デフォなし)if(n<=0): return 0P = 1for i in range(1,n+1):P *= iif(m>0): P %= mreturn Pdef nCmMOD(A,B,Mod):# a conb b を Mod で割った余り 1絡みの挙動に注意する。# 大量にほしいときは階乗逆元を使うやつを持ってくる。num,den=1,1for i in range(B):num*=(A-i)den*=(i+1)num%=Modden%=Modreturn (num*pow(den,Mod-2,Mod))%Moddef comb_table(N):# nCkのテーブルを作る, nCk = C[n][k]C = [[0 for i in range(N+1)] for j in range(N+1)]C[0][0] = 1for n in range(1,N+1):for k in range(n+1):C[n][k] = C[n-1][k-1] + C[n-1][k]return Cdef nHk(A,B,Mod):# 重複組合せ:1~nの中から重複を許してk個のものを選ぶ組合せreturn nCmMOD(A-1+B,A-1,Mod)def factorization(n):# 素因数分解、1に注意arr = []; temp = nfor i in range(2, int(-(-n**0.5//1))+1):if temp%i==0:cnt=0while temp%i==0:cnt+=1temp //= iarr.append([i, cnt])if temp!=1: arr.append([temp, 1])if arr==[]: arr.append([n, 1])return arrdef get_primes(n: int) -> list:# n以下の素数表sieve=[1]*nfor i in range(3,int(n**0.5)+1,2):if sieve[i]:sieve[i*i::2*i] = [0] * ((n-i*i-1)//(2*i)+1)return [2] + [i for i in range(3,n,2) if sieve[i]]#@lru_cache(maxsize=2*10**5)def division(a, b, m):# a÷bをmod mで求める 大量に使うときはメモ化return (a * pow(b, m - 2, m)) % mmemod=defaultdict(lambda:-1)def gcd(a,b):# 最大公約数while b!=0: a,b = b,a%breturn adef lcm(a,b):# 最小公倍数return(a*b // gcd(a,b))def make_divisors(n):# nの約数列挙divisors = []for i in range(1, int(n**0.5)+1):if n % i == 0:divisors.append(i)if i != n // i:divisors.append(n//i)#divisors.sort()return(divisors)def ran(A):# ランレングス圧縮L = list(A); T = []for i in range(len(L)):if i==0: T.append([L[0],1])else:if L[i]==L[i-1]: T[-1][1]+=1else: T.append([L[i],1])#return Tans1,ans2=[],[]for i in range(len(T)):ans1.append(T[i][0]) #種目ans2.append(T[i][1]) #個数return ans1,ans2def dot(P,Q,a,b,c):# P(a,b), Q(b,c) の行列積, abcに1が入るときは注意ret = LL(a,c)for i in range(a):for j in range(c):for k in range(b):ret[i][j] += P[i][k] * Q[k][j]return retdef Trans(arr,h,w):# 配列の転置ret=LL(w,h)for i in range(h):for j in range(w): ret[j][i] = arr[i][j]return ret# Union-Find---------------------------------------#Root=list(range(N))#Size=[1]*Ndef find_root(root,x):y = root[x]if x == y: return xz = find_root(root,y)root[x] = zreturn zdef merge(root,size,x,y):x = find_root(root,x)y = find_root(root,y)if x == y: returnsx,sy = size[x],size[y]if sx < sy:sx,sy = sy,sxx,y = y,xroot[y] = xsize[x] += sydef getValue(root,size,x):return size[find_root(root,x)]def same(root,x,y):return (find_root(root,x)==find_root(root,y))# itertools"""array=[1,2,3]PMT = permutations(array) #順列#123,132,213,231,312,321PMT2 = permutations(array,2)#12,13,21,23,31,32CMB1 = combinations(array,2) #組合せ#12,13,23CMB2 = combinations_with_replacement(array,2) #重複組合せ#11,12,13,22,23,33def all_comb(array):#全組合せ(個数1~N)ret=[]for i in range(len(array)+1):ret+=list(combinations(array,i))return ret#-,1,2,3,12,13,23,123array2=[0,1]PRD1 = product(array2,repeat=3) #直積#000,001,010,011,100,101,110,111""""""#AN=II()print(5*(3+math.sqrt(5))*N**3/12)""""""#BN=II()A=LI()""""""def sft(x):return x//2 + (2**15 * (x%2))for S in range(3):print(S)for i in range(4):print(S, sft(S), "{:b}".format(sft(S)))S=sft(S)""""""2**16まで、どのような変化をたどるのかを見る""""""#CN,M=MI()G=LB(N)E=[]for i in range(M):u,v=MI()u-=1v-=1u,v=min(u,v),max(u,v)G.append((u,i))G.append((v,i))E.append((u,v))# 多分逆にやるUFのやつ# 辺xがi番目の操作によって取り除かれているのかのiを探す。Root=list(range(N))Size=[1]*NSCORE=[0]*Nfor x in range(M)[::-1]:(u,v)=E[x]if same(Root,u,v):U,V=find_root(Root,u), find_root(Root,v)#print('a')new = SCORE[U] + 1SCORE[U] = newSCORE[V] = newelse:#print('b')U,V=find_root(Root,u), find_root(Root,v)merge(Root, Size, u, v)new = max(SCORE[U], SCORE[V]) + 1SCORE[U] = newSCORE[V] = new#print(u,v,SCORE)print(max(SCORE))"""#DN=II()S=list(input())# 0番目スタートで固める場合、1,2の3通りを試すc=[0,0,0]o=[0,0,0]n=[0,0,0]for i in range(3*N):if S[i]=='c':#print('c', i)c[i%3]+=1elif S[i]=='o':#print('o', i)o[i%3]+=1elif S[i]=='n':#print('n', i)n[i%3]+=1A0 = min([c[0],o[1],n[2]])A1 = min([c[1],o[2],n[0]])A2 = min([c[2],o[0],n[1]])ANS = sum([A0,A1,A2])print(ANS)#print(c,o,n)