結果
| 問題 | No.1994 Confusing Name |
| ユーザー |
 faculty_of_900
|
| 提出日時 | 2023-01-17 22:14:47 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
AC
|
| 実行時間 | 967 ms / 2,000 ms |
| コード長 | 10,831 bytes |
| コンパイル時間 | 475 ms |
| コンパイル使用メモリ | 11,764 KB |
| 実行使用メモリ | 56,632 KB |
| 最終ジャッジ日時 | 2023-08-31 00:56:04 |
| 合計ジャッジ時間 | 16,416 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 44 ms
11,376 KB |
| testcase_01 | AC | 40 ms
11,356 KB |
| testcase_02 | AC | 41 ms
11,212 KB |
| testcase_03 | AC | 40 ms
11,312 KB |
| testcase_04 | AC | 41 ms
11,340 KB |
| testcase_05 | AC | 46 ms
11,736 KB |
| testcase_06 | AC | 54 ms
12,168 KB |
| testcase_07 | AC | 43 ms
11,352 KB |
| testcase_08 | AC | 50 ms
11,748 KB |
| testcase_09 | AC | 53 ms
12,232 KB |
| testcase_10 | AC | 47 ms
11,760 KB |
| testcase_11 | AC | 46 ms
11,812 KB |
| testcase_12 | AC | 736 ms
35,420 KB |
| testcase_13 | AC | 928 ms
56,420 KB |
| testcase_14 | AC | 921 ms
56,412 KB |
| testcase_15 | AC | 748 ms
38,940 KB |
| testcase_16 | AC | 672 ms
36,348 KB |
| testcase_17 | AC | 752 ms
38,372 KB |
| testcase_18 | AC | 964 ms
56,608 KB |
| testcase_19 | AC | 967 ms
56,556 KB |
| testcase_20 | AC | 959 ms
56,632 KB |
| testcase_21 | AC | 215 ms
18,172 KB |
| testcase_22 | AC | 120 ms
14,864 KB |
| testcase_23 | AC | 834 ms
38,856 KB |
| testcase_24 | AC | 814 ms
38,384 KB |
| testcase_25 | AC | 524 ms
34,036 KB |
| testcase_26 | AC | 290 ms
22,780 KB |
| testcase_27 | AC | 769 ms
36,708 KB |
| testcase_28 | AC | 567 ms
34,304 KB |
| testcase_29 | AC | 104 ms
14,460 KB |
| testcase_30 | AC | 616 ms
34,416 KB |
ソースコード
# ライブラリインポート------------------------------------------
import math
import collections
#import statistics
from copy import deepcopy
from collections import defaultdict,deque
from sys import exit,setrecursionlimit
from heapq import heapify,heappush,heappop
from bisect import bisect_left,bisect_right,insort
from itertools import product,permutations,combinations,accumulate,combinations_with_replacement
from decimal import Decimal
#from numpy import array,matrix,dot,T
from functools import lru_cache
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
from string import ascii_uppercase, ascii_lowercase
# お決まり------------------------------------------------
INF=10**18 # まれに足りない場合もある
MOD=10**9+7
mod=998244353
def 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_uppercase
alpha=ascii_lowercase
setrecursionlimit(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 ret
def Banhei(hight,width,LLS,wall='#'): # 01マップなら0
ret=[[wall]*(width+2)]
for i in range(hight):
ret.append([wall]+LLS[i]+[wall])
ret.append([wall]*(width+2))
return ret
def 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 ret
def ALLI(): # 何個与えられるかわからないとき
res=[]
while True:
try: res.append(LI())
except: break
return res
# 出力カンペ--------------------------------------------
"""
print(''.join(['a', 'b', 'c'])) # abc
print("{: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,'-')) # 右詰め ---------python
print(str(29).rjust(10,'0')) # 10桁ゼロ埋め 0000000029
print("{:.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 B
def fac(n, m=0):
# nの階乗 | m:mod(デフォなし)
if(n<=0): return 0
P = 1
for i in range(1,n+1):
P *= i
if(m>0): P %= m
return P
def nCmMOD(A,B,Mod):
# a conb b を Mod で割った余り 1絡みの挙動に注意する。
# 大量にほしいときは階乗逆元を使うやつを持ってくる。
num,den=1,1
for i in range(B):
num*=(A-i)
den*=(i+1)
num%=Mod
den%=Mod
return (num*pow(den,Mod-2,Mod))%Mod
def 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] = 1
for 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 C
def nHk(A,B,Mod):
# 重複組合せ：1~nの中から重複を許してk個のものを選ぶ組合せ
return nCmMOD(A-1+B,A-1,Mod)
def factorization(n):
# 素因数分解、1に注意
arr = []; temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1: arr.append([temp, 1])
if arr==[]: arr.append([n, 1])
return arr
def get_primes(n: int) -> list:
# n以下の素数表
sieve=[1]*n
for 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)) % m
memod=defaultdict(lambda:-1)
def gcd(a,b):
# 最大公約数
while b!=0: a,b = b,a%b
return a
def 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]+=1
else: T.append([L[i],1])
#return T
ans1,ans2=[],[]
for i in range(len(T)):
ans1.append(T[i][0]) #種目
ans2.append(T[i][1]) #個数
return ans1,ans2
def 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 ret
def 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]*N
def find_root(root,x):
y = root[x]
if x == y: return x
z = find_root(root,y)
root[x] = z
return z
def merge(root,size,x,y):
x = find_root(root,x)
y = find_root(root,y)
if x == y: return
sx,sy = size[x],size[y]
if sx < sy:
sx,sy = sy,sx
x,y = y,x
root[y] = x
size[x] += sy
def 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,321
PMT2 = permutations(array,2)
#12,13,21,23,31,32
CMB1 = combinations(array,2) #組合せ
#12,13,23
CMB2 = combinations_with_replacement(array,2) #重複組合せ
#11,12,13,22,23,33
def 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,123
array2=[0,1]
PRD1 = product(array2,repeat=3) #直積
#000,001,010,011,100,101,110,111
"""
"""
#A
X=II()
P=0
D=[2,2,-1,-1,2,-1,-1]
B=[2,2,1,1,2,1,1]
A=[-1]*100
S=0
for i in range(100):
P+=D[i%7]
S+=B[i%7]
if A[P]==-1:
A[P]=S
print(A[X])
"""
"""
#B
N=II()
A=LI()
ANS=1000
for i in range(N-1):
ANS *= (1000-A[i])/1000
ANS = 1000- ANS
print(ANS)
"""
"""
#C
N=II()
S=[input() for i in range(N)]
# 最初からのロリハと最後からの逆ロリハがギャップ1まで同じならよいということかな
from random import randint
class RollingHash():
def __init__(self, s, base, mod):
self.mod = mod
self.pw = pw = [1]*(len(s)+1)
l = len(s)
self.h = h = [0]*(l+1)
v = 0
for i in range(l):
h[i+1] = v = (v * base + ord(s[i])) % mod
v = 1
for i in range(l):
pw[i+1] = v = v * base % mod
def get(self, l, r):
return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
A=[]
B=[]
R1,R2 = randint(10**8, 10**9), randint(10**8, 10**9)
for i in range(N):
HA1 = RollingHash(S[i], 37, R1)
HA2 = RollingHash(S[i], 26, R2)
HB1 = RollingHash(S[i][::-1], 37, R1)
HB2 = RollingHash(S[i][::-1], 26, R2)
A.append([HA1,HA2])
B.append([HB1,HB2])
def check(x, y):
"""
"""
#D
N,M=MI()
AB=[]
C=set()
D=defaultdict(lambda:-1)
# できるだけ「近道」を使ったほうが良い。
# 座標圧縮してDPにすることを考える
for i in range(M):
a,b=MI()
a-=1
b-=1
AB.append([a,b])
C.add(a)
C.add(b)
C=sorted(list(C))
cnt=0
for i in C:
D[i]=cnt
cnt+=1
#print(D)
# 問題は以下のようになった。
# M個の宝物があり、すべて価値は1で、時間D[ai]~D[bi]の間を探索に使うことで手に入れることができる。
# 最高スコアはなにか。
ANS=2*(N-1)
S=[]
for [a,b] in AB:
S.append([D[a],D[b]])
S=sorted(S)
print(S)
dp=[0]*210000
c=0
for [a,b] in S:
while c<a:
dp[a] = max(dp[a], dp[c])
c+=1
dp[a] = max(dp[a], dp[a-1])
dp[b] = max(dp[b], dp[a]+1)
print(a,b,dp[:15])
#print(dp[:15])
print(ANS-max(dp))
"""
"""
#C
N=II()
S=LB(11)
for i in range(N):
s=input()
S[len(s)].append(s)
# 長さの同じ文字列x,yがちょうど1文字だけ異なるかどうかを確かめたい。
# でも、2重のループを使うことは許されない。
# 文字xとyが1文字だけ違う→
for i in range(11):
"""
N=II()
S=[input() for i in range(N)]
D=DD()
for i in S:
D[i]+=1
# 完全に同じものの排除をどうにかしよう
for j in range(len(i)):
s = i[:j] + "?" + i[j+1:]
#print(s)
D[s] += 1
for i in S:
ANS=0
for j in range(len(i)):
s = i[:j] + "?" + i[j+1:]
ANS += D[s] - D[i]
print(ANS)