#833721 (Python3) No.1995 CHIKA Road

提出ソース

結果

問題	No.1995 CHIKA Road
ユーザー	faculty_of_900
提出日時	2023-01-17 21:57:15
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	1,106 ms / 2,000 ms
コード長	10,158 bytes
コンパイル時間	204 ms
コンパイル使用メモリ	13,696 KB
実行使用メモリ	64,748 KB
最終ジャッジ日時	2024-06-10 23:46:27
合計ジャッジ時間	18,430 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	49 ms 14,720 KB
testcase_01	AC	47 ms 14,720 KB
testcase_02	AC	64 ms 14,592 KB
testcase_03	AC	48 ms 14,592 KB
testcase_04	AC	46 ms 14,592 KB
testcase_05	AC	47 ms 14,464 KB
testcase_06	AC	113 ms 17,900 KB
testcase_07	AC	286 ms 24,500 KB
testcase_08	AC	50 ms 14,720 KB
testcase_09	AC	49 ms 14,720 KB
testcase_10	AC	704 ms 34,692 KB
testcase_11	AC	1,106 ms 64,748 KB
testcase_12	AC	944 ms 49,984 KB
testcase_13	AC	354 ms 28,148 KB
testcase_14	AC	375 ms 28,724 KB
testcase_15	AC	970 ms 60,544 KB
testcase_16	AC	153 ms 19,456 KB
testcase_17	AC	543 ms 33,992 KB
testcase_18	AC	990 ms 49,732 KB
testcase_19	AC	1,013 ms 49,496 KB
testcase_20	AC	511 ms 32,220 KB
testcase_21	AC	467 ms 31,040 KB
testcase_22	AC	900 ms 48,244 KB
testcase_23	AC	278 ms 24,800 KB
testcase_24	AC	768 ms 44,900 KB
testcase_25	AC	177 ms 20,320 KB
testcase_26	AC	315 ms 26,832 KB
testcase_27	AC	745 ms 44,148 KB
testcase_28	AC	436 ms 31,020 KB
testcase_29	AC	911 ms 48,636 KB
testcase_30	AC	168 ms 19,984 KB
testcase_31	AC	104 ms 17,296 KB
testcase_32	AC	210 ms 22,600 KB
testcase_33	AC	736 ms 43,484 KB
testcase_34	AC	115 ms 17,928 KB
testcase_35	AC	298 ms 25,596 KB
testcase_36	AC	342 ms 27,956 KB
testcase_37	AC	892 ms 47,288 KB
testcase_38	AC	574 ms 36,332 KB
testcase_39	AC	98 ms 17,104 KB

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

ソースコード

raw source code

# ライブラリインポート------------------------------------------
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))

yukicoder

結果

テストケース

ソースコード