灰色の戯言（AtCoder Beginner Contest 212 C - Min Difference)

私はＡｔＣｏｄｅｒの灰色です。現在、茶色を目指して健闘中です。

AtCoder Beginner Contest 212 C - Min Difference

 

ただ、私の理解度が低すぎて今回練習で解いたＡＢＣ２１２のＣ問題の解説をいくら読んでも理解できませんでした。しかし、奮闘の結果自力でなんとか解くことができました。

あくまでも今後のために記録として残しておきたいと思ったので、自分で解説を書くことにしました。

開発言語はPythonです。

n , m = map(int,input().split())

a = list(map(int,input().split()))

b = list(map(int,input().split()))

c_min = 10**9

for i in range(n):

    for j in range(m):

        c_min = min(c_min,abs(a[i]-b[j]))

print(c_min)

上記の全検索だとタイムオーバー(TLE)になってしまいます。

そこで

Aリスト、Ｂリスト共にソートしたものを、ｉ及びｊの小さい順にＡとＢを比較、ＡまたはＢの小さい側は一つ右にシフトして、再びＡとＢを比較します。それを繰り返します。

①Ａ１とＢ１を比較、Ａが小さい

②Ａが右に移動（ｉ　＋＝　１）

③Ａ２とＢ１を比較、Ｂが小さい

④Ｂが右に移動（ｊ　＋＝　１）

⑤Ａ２とＢ２を比較、Aが小さい

⑥Ａが右に移動（ｉ　＋＝　１）

⑦Ａ３とＢ２を比較

その間にＡｉ－Ｂｊの値を比較して、最も差が小さい数字を出力します。

n , m  = map(int,input().split())

a = list(map(int,input().split()))

b = list(map(int,input().split()))

a.sort()

b.sort()

c = 10**9

i = j = 0

 

while i < n and j < m:

    c = min(c,abs(a[i]-b[j]))

    if a[i] < b[j]:

        i += 1

    else:

        j += 1

print(c)