ABC212 C - Min Difference を解いてみた

13730 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク

2重 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.py
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)

改善点

・A/B の重複削除の記述を排除
仮に重複があったともして前述にあるように O(4*10^5) なので計算量は問題にならないし、答えが変わることはない。
・try/except の記述を削除
辞書の in演算は O(1) なのでガンガン使うことで記述が計算量を気にせず、シンプルに書ける。