🔖
AtCoder ARC121 個人的メモ
所感
a1完
終了6分でbをacした
悔しい
初のレート4桁到達
嬉しい
A - 2nd Greatest Distance
全部の家同士の距離を求めて、それをソートするのは
最も遠い家の組み合わせは
簡単のため、家同士の距離がxの値のみで定まるとする。
昇順(小さい順)でソート済みの家の座標xを
このとき最も遠い家同士の距離は
二番目に遠い家同士の距離は以下の3つの組み合わせのどれか
|x_1-x_{N-1}| |x_2-x_N| |x_2-x_{N-1}|
よって、この3つの内最大の値が2番目に遠い家同士の距離。
今回はxだけではなくyもあるので、2番目に遠い家同士の距離の候補は6つになる。
なのでその候補の内、距離が最大になる家の組とは違う組み合わせの家かつ2番目に距離が最大になる家の組み合わせを探す。
N = int(input())
X, Y = [], []
for i in range(N):
x, y = map(int, input().split())
X.append((x, i))
Y.append((y, i))
X.sort()
Y.sort()
candidate = []
for xa, ia in X[-2:]:
for xb, ib in X[:2]:
candidate.append([xa - xb, {ia, ib}])
for ya, ia in Y[-2:]:
for yb, ib in Y[:2]:
candidate.append([ya - yb, {ia, ib}])
candidate.sort(reverse=True)
_, max_pair = candidate[0]
for distance, pair in candidate[1:]:
if max_pair != pair:
print(distance)
break
B - RGB Matching
ペアを作る際、同じ色の2匹を選べるなら選んだほうが良さそう。
犬の総計は偶数なので、3色の数は(偶数、偶数、偶数)か(奇数、奇数、偶数)のいずれかと分かる。
前者の場合は、全ての色において同じ色どうしでペアを作れるので、答えは0でおｋ。
後者の場合は以下の2つの内のどっちかが最適。
- 奇数の色どうしから1匹ずつ選んで1つの色が異なるペアを作る。
- 奇数の色2色から1匹ずつと偶数の色1色から2匹選んで、2つの色が異なるペアを作る。
これを実装すればおｋ。
しかし、最適なペアを探す際に全探索するとTLEしそうなので高速化する。
最適なペアはできる限り美しさの差が小さいペアとなるので、二分探索で高速化できる。
acしたときのコードがとても汚かったので、かなり修正したコードを載せておく。
from bisect import bisect_left
def find_closest_val(lst: list, val: int):
"""
数列lst内で数値valに最も近い値を二分探索で探し、valとの絶対値の差を返す
"""
# leftはlst内のval未満でvalに最も近い要素のインデックス
left = bisect_left(lst, val)
res = abs(val - lst[left - 1])
if left < len(lst):
res = min(res, abs(val - lst[left]))
return res
N = int(input())
lst = [[] for _ in range(3)]
color = "RGB"
for _ in range(N * 2):
a, c = input().split()
lst[color.index(c)].append(int(a))
A, B, C = lst
while len(C) % 2 == 1: # Cが偶数個の色になるようにA,B,Cの名前を変える
C, A, B = A, B, C
if len(A) % 2 == 0: # (A,B,C)=(偶,偶,偶)の場合は答え0
print(0)
exit()
# 以降(A,B,C)=(奇,奇,偶)
A.sort() # 二分探索のためのソート
B.sort()
# A,Bから1つずつ選ぶ場合
ans = min(find_closest_val(B, a) for a in A)
# A,CとB,Cで1つずつ選ぶ場合
if C:
res = 0
res += min(find_closest_val(A, c) for c in C)
res += min(find_closest_val(B, c) for c in C)
ans = min(ans, res)
print(ans)
修正前のコード
N = int(input())
INF = 10 ** 18
red = []
green = []
blue = []
for _ in range(N * 2):
a, i = input().split()
a = int(a)
if i == "R":
red.append(a)
elif i == "G":
green.append(a)
else:
blue.append(a)
if all(len(lst) % 2 == 0 for lst in (red, green, blue)):
print(0)
exit()
elif len(red) % 2 == 0:
C = red
A = green
B = blue
elif len(green) % 2 == 0:
C = green
A = red
B = blue
else:
C = blue
A = red
B = green
if len(A) > len(B):
A, B = B, A
A.sort()
B.sort()
# xyの組み合わせ
ans = INF
for a in A:
left = 0
right = len(B)
while right - left > 1:
mid = left + right
mid //= 2
if B[mid] < a:
left = mid
else:
right = mid
ans = min(ans, abs(a - B[left]))
if left + 1 < len(B):
ans = min(ans, abs(a - B[left + 1]))
# zx,zy
res = 0
pick_i = -1
for lst in (A, B):
tmp = INF
for i in range(len(C)):
left = 0
right = len(lst)
while right - left > 1:
mid = left + right
mid //= 2
if lst[mid] < C[i]:
left = mid
else:
right = mid
cal = abs(C[i] - lst[left])
if tmp > cal:
tmp = cal
pick_i = i
if left + 1 < len(lst):
cal = abs(C[i] - lst[left + 1])
if tmp > cal:
tmp = cal
pick_i = i
if pick_i != -1:
C[-1], C[pick_i] = C[pick_i], C[-1]
C.pop()
res += tmp
ans = min(ans, res)
print(ans)
参考
二分探索の実装 コードの修正
Discussion