結果
問題 | No.1818 6 Operations |
ユーザー | ygd. |
提出日時 | 2022-01-22 20:12:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 444 ms / 2,500 ms |
コード長 | 1,815 bytes |
コンパイル時間 | 708 ms |
コンパイル使用メモリ | 82,816 KB |
実行使用メモリ | 180,736 KB |
最終ジャッジ日時 | 2024-05-05 20:21:12 |
合計ジャッジ時間 | 9,540 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
51,840 KB |
testcase_01 | AC | 43 ms
59,648 KB |
testcase_02 | AC | 36 ms
52,736 KB |
testcase_03 | AC | 35 ms
52,352 KB |
testcase_04 | AC | 36 ms
52,736 KB |
testcase_05 | AC | 36 ms
52,480 KB |
testcase_06 | AC | 35 ms
52,096 KB |
testcase_07 | AC | 34 ms
52,224 KB |
testcase_08 | AC | 181 ms
109,952 KB |
testcase_09 | AC | 288 ms
134,972 KB |
testcase_10 | AC | 150 ms
110,288 KB |
testcase_11 | AC | 174 ms
107,884 KB |
testcase_12 | AC | 241 ms
112,896 KB |
testcase_13 | AC | 185 ms
113,920 KB |
testcase_14 | AC | 217 ms
112,924 KB |
testcase_15 | AC | 255 ms
132,776 KB |
testcase_16 | AC | 206 ms
112,800 KB |
testcase_17 | AC | 285 ms
135,808 KB |
testcase_18 | AC | 406 ms
157,824 KB |
testcase_19 | AC | 363 ms
157,440 KB |
testcase_20 | AC | 395 ms
175,684 KB |
testcase_21 | AC | 425 ms
177,280 KB |
testcase_22 | AC | 307 ms
158,456 KB |
testcase_23 | AC | 435 ms
180,736 KB |
testcase_24 | AC | 325 ms
158,592 KB |
testcase_25 | AC | 441 ms
180,396 KB |
testcase_26 | AC | 336 ms
158,080 KB |
testcase_27 | AC | 394 ms
158,336 KB |
testcase_28 | AC | 195 ms
110,336 KB |
testcase_29 | AC | 183 ms
108,128 KB |
testcase_30 | AC | 401 ms
157,580 KB |
testcase_31 | AC | 369 ms
180,088 KB |
testcase_32 | AC | 444 ms
179,840 KB |
ソースコード
import sys #input = sys.stdin.readline #文字列につけてはダメ input = sys.stdin.buffer.readline #文字列につけてはダメ #sys.setrecursionlimit(1000000) #import bisect #import itertools #import random #from heapq import heapify, heappop, heappush #from collections import defaultdict #from collections import deque #import copy #import math #from functools import lru_cache #@lru_cache(maxsize=None) #MOD = pow(10,9) + 7 #MOD = 998244353 #dx = [1,0,-1,0] #dy = [0,1,0,-1] def Levenshtein_distance(A,B): #dp[i][j], Aがi文字目、Bがj文字目までにおける最小処理回数 INF = pow(10,18) n = len(A); m = len(B) dp = [[INF]*(m+1) for _ in range(n+1)] #初期化の方法が特殊。片方が0でもう片方がi文字なら最小処理回数はi。 for i in range(n+1): dp[i][0] = i for i in range(m+1): dp[0][i] = i for i in range(n): #i = 0つまり、0文字目なのでdp[1][1]からスタート for j in range(m): if A[i] == B[j]: #同じ場合そのままか、片方が一つずれているところから追加挿入。 dp[i+1][j+1] = min(dp[i][j],dp[i][j+1]+1,dp[i+1][j]+1) else: #異なる場合i文字目を交換か、片方が一つずれているところから追加挿入。 dp[i+1][j+1] = min(dp[i][j]+1,dp[i][j+1]+1, dp[i+1][j]+1) return dp[n][m] def change(X): ret = [] for x in X: ret.append(0) for _ in range(x): ret.append(1) return ret def main(): N,M = map(int,input().split()) A = list(map(int,input().split())) B = list(map(int,input().split())) C = change(A) D = change(B) #print(C,D) ans = Levenshtein_distance(C,D) print(ans) if __name__ == '__main__': main()