---
tags: Programming Contest
---
# AtCoder Beginner Contest 181 題解
[題目連結](https://atcoder.jp/contests/abc181)
## 心得
因為沒同學／朋友要一起參戰，比賽時只來看了一圈題目沒 submit。
## A, B, C
水題。
## D. Hachi
看完題目想說這麼簡單，怎麼 Standings 上一堆人都先 WA 才 AC，看我一次 AC，然後我就 WA 了三次 (┛ಸ_ಸ)┛彡┻━┻
基本想法就是枚舉 8 在 1000 以內的所有倍數，看有沒有一個倍數 x 所需要的 digits 能被 S 滿足。
這個解法的問題在於 S < 1000 時會有問題，例如 S = '516'，答案應該要是 No，但按上述方法會在 x = 16 時發現可以滿足。
一個解決的方法就是分 len(S) = 1, len(S) = 2, len(S) = 3, len(S) > 3 的情況分別討論。我這邊的解法是利用 S 中不可能有 0 的特性，將 x 補前綴 0，補到 min(len(S), 3)，再去看 S 能不能滿足 x 的 digits。
```python
from collections import defaultdict
S = input()
cnt = defaultdict(int)
for c in S:
cnt[c] += 1
for x in range(8, 1000, 8):
strx = str(x).ljust(min(len(S), 3), '0')
need = defaultdict(int)
for c in strx:
need[c] += 1
if all(cnt[c] >= need[c] for c in need.keys()):
print('Yes')
break
else:
print('No')
```
## E. Transformable Teacher
若給定偶數個數字 A，兩兩配對，使差的總和最小化的方法為：
設 S = sorted(A)，則 S[i] 與 S[i ^ 1] 配對。以下給出證明。
設有四個數字 `x < y < z < w`，那我們配對的方式有 3 種：
1. `[x, y], [z, w]: (w - z) + (y - x)`
2. `[x, z], [y, w]: (w - y) + (z - x)`
3. `[x, w], [y, z]: (z - y) + (w - x)`
每一種配對所得到的差的總和都有 `+ w - x`，讓我們將之消掉：
1. `[x, y], [z, w]: (y - z)`
2. `[x, z], [y, w]: (z - y)`
3. `[x, w], [y, z]: (z - y)`
明顯第一種配對方式是最小。
這個結論引導我們設計出這樣的方法：
1. 將 H 由小排到大
2. 預計算 `pref[i]` = `H[:i]` 從左至右兩兩配對的結果，`pref[i]` 只在 `i` 是奇數時有效
3. 預計算 `suff[i]` = `H[-i:]` 從右至左兩兩配對的結果，`suff[i]` 只在 `i` 是奇數時有效
4. 枚舉 w，二分搜 w 在 H 中的位置為 `idx`。
5. 若 `idx` 是偶數，則 w $\cup$ H 的結果為 `pref[idx - 1] + suff[idx + 1] + (H[idx] - w)`
6. 若 `idx` 是奇數，則 w $\cup$ H 的結果為 `pref[idx - 2] + suff[idx] + (w - H[idx - 1])`
後面這些數字的部份，拿範測推一下即可。
小心 `idx` 是 0 或 N 的情況，我這邊將 `pref`, `suff` 超出界限的部份設成 0。
```python
from bisect import bisect_left
from collections import defaultdict
N, M = map(int, input().split())
H = [int(x) for x in input().split()]
W = [int(x) for x in input().split()]
H.sort()
pref = defaultdict(int)
pref[0] = -H[0]
for i in range(1, N):
if i % 2 == 1:
pref[i] = pref[i - 1] + H[i]
else:
pref[i] = pref[i - 1] - H[i]
suff = defaultdict(int)
suff[N - 1] = H[N - 1]
for i in range(N - 2, -1, -1):
if i % 2 == 1:
suff[i] = suff[i + 1] - H[i]
else:
suff[i] = suff[i + 1] + H[i]
ans = 10 ** 9
for w in W:
idx = bisect_left(H, w)
if idx % 2 == 1:
val = pref[idx - 2] + suff[idx] + w - H[idx - 1]
else:
val = pref[idx - 1] + suff[idx + 1] + H[idx] - w
ans = min(ans, val)
print(ans)
```
## F. Silver Woods
Credit: 討論區 unstoppable_1000 給出的[題解](https://codeforces.com/blog/entry/84246#comment-717623)。
二分搜圓的半徑 r，然後枚舉每一個 nail，然後看他跟其他 nail 或邊界是不是距離 2r 以內，若是的話，說明圓是通不過他們之間的 gap 的，將他們視為一群。最後看上方邊界與下方邊界是不是一群就知道這個 r 可不可行。
想不到 Disjoint set 可以用在這種地方，拿來判斷上方邊界與下方邊界有沒有連通，學到了。
```python
from math import sqrt
class DisjoinSet:
def __init__(self, N):
self.par = [-1] * N
self.sz = [1] * N
def root(self, x):
if self.par[x] < 0:
return x
else:
self.par[x] = self.root(self.par[x])
return self.par[x]
def unite(self, a, b):
a = self.root(a)
b = self.root(b)
if a == b:
return
if self.sz[a] > self.sz[b]:
a, b = b, a
self.par[a] = b
self.sz[b] += self.sz[a]
def same(self, a, b):
return self.root(a) == self.root(b)
def size(self, x):
return self.sz[self.root(x)]
def __str__(self):
from collections import defaultdict
clusters = defaultdict(list)
for x in range(N):
clusters[self.root(x)].append(x)
return str(list(clusters.values()))
N = int(input())
xs, ys = [], []
for _ in range(N):
x, y = map(float, input().split())
xs.append(x)
ys.append(y)
def check(r):
dsu = DisjoinSet(N + 2)
for i in range(N):
for j in range(i + 1, N):
if sqrt((xs[i] - xs[j]) ** 2 + (ys[i] - ys[j]) ** 2) < 2 * r:
dsu.unite(i, j)
for i in range(N):
if abs(ys[i] - 100) < 2 * r:
dsu.unite(i, N + 0) # upper boundary
if abs(ys[i] - (-100)) < 2 * r:
dsu.unite(i, N + 1) # lower boundary
return dsu.root(N + 0) != dsu.root(N + 1)
lb, ub = 0, 200
for _ in range(50):
m = (lb + ub) / 2
if check(m):
lb = m
else:
ub = m
print('{:.9f}'.format(lb))
```
:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::
Sign in with Wallet
Connect another wallet