ABC057-B - Checkpoints を解く

ABC057-B - Checkpoints

平面状にいる複数の人を、与えられた複数のチェックポイントのいずれかに

移動させる。そのときの移動距離の総和の最小値を求める問題

人の数とチェックポイントの数はそれぞれ最大で50なので

総当たりで距離を計算しても充分間に合う（50 × 50 = 2500 で最大 2500 通り）

距離はマンハッタン距離で求める必要がある

(a,b) と (x,y) のマンハッタン距離は |x - a| + |y - b| で表すことができる

（参考：ABC035-B - ドローン を解く - 考えて競プロする ）

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N,M=map(int,input().split())

l1=[]
for i in range(N):
  l1.append(list(map(int,input().split())))

l2=[]
for i in range(M):
  l2.append(list(map(int,input().split())))

for i in range(N):
  # 距離の最小値（1つ目のチェックポイントへの距離で初期化している）
  d=abs(l1[i][0]-l2[0][0])+abs(l1[i][1]-l2[0][1])

  # 最も近いチェックポイントの番号（1番目で初期化）
  b=1

  # 2つ目以降のチェックポイントへの距離を求める
  for j in range(1,M):
    x=abs(l1[i][0]-l2[j][0])+abs(l1[i][1]-l2[j][1])

    # 距離がより小さい場合のみ更新
    if x<d:
      d=x
      # 0-index なので調整するために +1 している
      b=j+1

  # チェックポイントの番号を出力
  print(b)

 

ABC-B 問題にしては実装が重い

入力値も多くて結構難しかった

提出結果はACでした