競プロ初中級者100問

Square869120Countest#6B - AtCoder Market

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_b

この問題は全探索を用いて部分点を得ることができます。満点解法には数学的思考が必要です。

方針

  • Aに対して最適な入口xは、Bに対して最適な出口yをそれぞれ独立に考えることができます。そのため、ここではAとxについて考察します。
  • 絶対値|x-A_i|の和が最小値となるようなxは、以下のような値です。
    • Aの要素数が奇数の場合・・・xをAの中央値とします。
    • Aの要素数が偶数の場合、中央の2値を(A_m,A_m+1)として、区間[A_m,A_m+1]のうちの任意の値とします。

実装上は結局、A[N//2]とすれば十分です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N = int(input())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort()
am = A[N//2]
bm = B[N//2]

ans = 0
for a,b in zip(A,B):
    ans += abs(a-b) # AからB
    ans += abs(a-am) # 入口からA
    ans += abs(b-bm) # 出口からB
print (ans)

記事情報

  • 投稿日：2020年5月8日
  • 最終更新日：2020年5月8日