ABC212 C - Min Difference를 풀어 보았습니다.
13230 단어 AtCoder파이썬AtCoderBeginnerContest
이중 for로 전체 탐색해도 되지만, 계산량이 4*10^10이 되어, TLE가 된다.
실 입을 찾기 위해, 우선 샘플을 확인해 본다.
개인적으로 주목한 것은 입력 예 3.
최소값을 찾는 것은 수열 A , 수열 B 중에서 값이 가까운 요소의 조합을 내면 좋지?
여기에서 더욱 도약이 들어갑니다.
그럼, 수열 A 와 수열 B 를 합체해 sort 하면 A[n]=>B[m] or B[m]=>A[n] 이 되는 줄이 반드시 있어,
그 중에서 차이가 최소가 되는 조합을 찾으면 좋지?
라고 말하는 것으로, 이것으로 갈 수 있었습니다.
MinDifference_1.py
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
A = list(set(A))#A の重複要素を排除
B = list(set(B))#B の重複要素を排除
#A,B を合体すると、ごちゃまぜで分からなくなるので、
#辞書で管理することにしました。
dicA = {}
dicB = {}
for i in range(len(A)):
dicA[A[i]] = 1#冒頭で set() してるので重複要素なし、要素は必ず 1 つ
for i in range(len(B)):
dicB[B[i]] = 1#冒頭で set() してるので重複要素なし、要素は必ず 1 つ
X = A + B # AとB を合体
X.sort() # sort する
ans = float("inf") # 無限大より小さいものを for で探す
#辞書はリストに無い key の所在を尋ねると Error を返します。
#if X[i] in dicA としても良かったかもだが、dicA/dicB の要素数が計算量として上乗せされる。
#そのため 2*10^5 x 2*10^5 となる可能性があるので記述は避けた。
#代わりに try / except を使って計算量を抑えた.
for i in range(len(X)-1):#=> X を端から確認し、X[i],X[i+1] の差分をcheck。
try:
if dicA[X[i]] == 1 and dicB[X[i+1]] == 1:#辞書で X[i],X[i+1] がそれぞれ A,B であることを確認
if abs(X[i]-X[i+1]) < ans:
ans = abs(X[i]-X[i+1])
except:#上記で Error で返したら、以下の処理に入る
try:
if dicB[X[i]]==1 and dicA[X[i+1]]==1:#辞書で X[i],X[i+1] がそれぞれ A,B であることを確認
if abs(X[i] - X[i + 1]) < ans:
ans = abs(X[i] - X[i + 1])
except:
pass#上記でもダメなら pass。次の検証に向かう
print(ans)
분명, 더 알기 쉽고 좋은 해법이 있을 것.
우선, 다른 사람의 해법도 읽으면서 이미지를 쌓아 보려고 한다.
감동하면 추기할지도.
이해가 어리석은지도 모르지만,
위의 경우의 계산량은 O(N)라고 생각하지만 다르지 않을까?
지식인의 조언이 있으면 도움이 될 것입니다 m (_ _) m
그때부터
아직도 적지만 여러가지 풀어 견식이 퍼졌다고 믿고, 재챌린지.
이하에서도 다녔다.
MinDifference_2.pyN,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
dicA = {}
dicB = {}
for n in range(N):
if A[n] not in dicA:
dicA[A[n]] = 0
dicA[A[n]] += 1
for m in range(M):
if B[m] not in dicB:
dicB[B[m]] = 0
dicB[B[m]] += 1
X = A + B
X.sort()
score = float("inf")
for i in range(N+M-1):#max O(4*10**5)
if X[i] in dicA and X[i+1] in dicB or X[i] in dicB and X[i+1] in dicA:
score = min(score,abs(X[i]-X[i+1]))
print(score)
개선점
· A/B 중복 삭제 설명을 제거합니다.
만일 중복이 있었다고 해도 전술에 있듯이 O(4*10^5)이므로 계산량은 문제가 되지 않고, 대답이 바뀌지 않는다.
· try/except의 설명 삭제
사전의 in연산은 O(1)이므로 강간 사용하는 것으로 기술이 계산량을 신경쓰지 않고, 간단하게 쓸 수 있다.
Reference
이 문제에 관하여(ABC212 C - Min Difference를 풀어 보았습니다.), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/AKpirion/items/f3f0708ae4b2af613d34
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
dicA = {}
dicB = {}
for n in range(N):
if A[n] not in dicA:
dicA[A[n]] = 0
dicA[A[n]] += 1
for m in range(M):
if B[m] not in dicB:
dicB[B[m]] = 0
dicB[B[m]] += 1
X = A + B
X.sort()
score = float("inf")
for i in range(N+M-1):#max O(4*10**5)
if X[i] in dicA and X[i+1] in dicB or X[i] in dicB and X[i+1] in dicA:
score = min(score,abs(X[i]-X[i+1]))
print(score)
Reference
이 문제에 관하여(ABC212 C - Min Difference를 풀어 보았습니다.), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/AKpirion/items/f3f0708ae4b2af613d34텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)