目次
AtCoder Beginner Contest 151 D～F問題メモ
D - Maze Master
問題
'.' と'#' からなる $H \times W$ のフィールドが与えられる'.' は道、'#' は壁で通れない- 道は2マス以上あり、全ての道は互いに繋がっている
- 道の中からスタートとゴールを決め、上下左右へ隣接する道への移動を距離1として、スタートからゴールまで最短距離で移動する
- スタートとゴールを適切に決めたとき、移動距離の最大値を求めよ
- $1 \le H,W \le 20$
解法
幅優先探索。
スタートが決められたとき、そこから最も遠いマスは、幅優先探索で最後に訪れたマスとなる。
よって、道である各マスをスタート地点として全て試し、最長移動距離の最大値が答え。
$H,W$ の上限が小さいので、スタート地点候補が最大400、1回の探索で探索するマスが最大400、あわせて160000回に比例する計算量で間に合う。
なお、木の直径を求めるように「適当な1マスから最遠点を求める」→「そこからの最遠点を求める」方法だと、ループがある場合は最適が保証されない。 たとえば以下の感じ。
..... (1,1)からスタートすると、最遠点は(4,4) .##.# →そこからの最遠点は(1,1) .##.# ....# しかし実際は、(1,5),(4,1) の組が最遠
from collections import deque
def bfs(field, s):
MOVE = [(0, 1), (1, 0), (0, -1), (-1, 0)]
q = deque([(0, s)])
dist = [[-1] * w for _ in range(h)]
d, i, j = -1, -1, -1
while q:
d, (i, j) = q.popleft()
if dist[i][j] != -1:
continue
dist[i][j] = d
for di, dj in MOVE:
ni, nj = i + di, j + dj
if not 0 <= ni < h or not 0 <= nj < w:
continue
if field[ni][nj] == '#':
continue
if dist[ni][nj] != -1:
continue
q.append((d + 1, (ni, nj)))
return d, i, j
h, w = map(int, input().split())
field = [input() for _ in range(h)]
ans = 0
for i in range(h):
for j in range(w):
if field[i][j] == '.':
d, i, j = bfs(field, (i, j))
ans = max(ans, d)
print(ans)
E - Max-Min Sums
問題
- 整数集合 $X$ に対し $f(X)=\max{X}−\min{X}$ と定義する
- $N$ 個の整数 $A_1,...,A_N$ が与えられる
- ここから $K$ 個を選び、それらからなる集合を $S$ とする
- 同じ値であっても添字が異なる要素を区別すると、そのような選び方は ${}_NC_K$ 通りある
- 全ての選び方についての $f(S)$ の合計を、$\mod{10^9+7}$ で求めよ
- $1 \le N \le 10^5$
- $|A_i| \le 10^9$
解法
maxとminを分けて考える。
ある複数の選び方 $S_1, S_2, S_3,...$ について、
\begin{align} f(S_1)+f(S_2)+f(S_3)+... &= \max{S_1} - \min{S_1} + \max{S_2} - \min{S_2} + \max{S_3} - \min{S_3} \\\\ &= (\max{S_1}+\max{S_2}+\max{S_3}+...)-(\min{S_1}+\min{S_2}+\min{S_3}+...) \end{align}
なので、こう考えればよい。
- 要素 $A_i$ が、$\max{S_k}$ となるような選び方は何通りか？ → $P_i$ とする
- 要素 $A_i$ が、$\min{S_k}$ となるような選び方は何通りか？ → $Q_i$ とする
すると、$A_i$ が答えに寄与するのは、$(P_i - Q_i) \times A_i$ となる。 これを全ての $i$ について足し合わせればよい。
$P_i,Q_i$ の求め方
考えやすくするため、ひとまず $A_i$ は全て異なるとする。 また、昇順にソートし、添字を0より振り直す。
$A_i$ が最大値となるためには、$K$ 個の内、自分は当然選ばれ、かつ自分より小さい要素のみが $K-1$ 個選ばれなければならない。
すると自分より小さい要素の個数は $i$ なので、パターン数は $P_i = {}_iC_{K-1}$ となる。
なお、$i \lt K-1$ の場合は、そのような選び方は不可能なので0となる。
$A_i$ に同じ要素がある場合を考える。 しかしこの場合も、要はソート後の配列で「選ばれた $K$ 個の中で $A_i$ が最も右になるパターン数」と言い換えられるので、同じ方法で数えあげることができる。
2つの"2"を、2a,2bと区別する
K=2
1 2a 2b 3 4
↑ ↑この2が最大となるのは、(1,2b) (2a,2b)
`----この2が最大となるのは、(1,2a)
最小値 $Q_i$ も、大小を逆に考えればよい。
def prepare(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return factorials, invs
n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
MOD = 10 ** 9 + 7
facts, invs = prepare(n, MOD)
max_sum = 0
min_sum = 0
for i, a in enumerate(aaa):
lo = i
hi = n - i - 1
if lo >= k - 1:
max_sum = (max_sum + facts[lo] * invs[k - 1] * invs[lo - k + 1] % MOD * a) % MOD
if hi >= k - 1:
min_sum = (min_sum + facts[hi] * invs[k - 1] * invs[hi - k + 1] % MOD * a) % MOD
print((max_sum - min_sum) % MOD)
F - Enclose All
問題
- 2次元平面上に $N$ 個の点 $(x_1,y_1),...,(x_N,y_N)$ が与えられる
- 最小包含円の半径を求めよ
- $2 \le N \le 50$
- $0 \le x_i,y_i \le 1000$
解法
AtCoderでは珍しめ(?)の典型問題。 でもこういう機会でもなければ触れないし、最小包含円をさらにアレンジしてこねくり回す問題は難しくてABC向けでは無いだろうので、いい機会と言えるかも。
PythonではOpenCVを非常に使いたくなるところだが、残念ながら入っていない。
最小包含円は様々な求め方があるが、1つの解法として「与えられた点から3点を選んできて、その最小包含円のうち、その3点以外も全て包含するもの」に一致する。
- 3点を選ぶと、その3点の最小包含円は一意に決まる
- 直角・鈍角三角形の場合は最長辺の中点
- 鋭角三角形の場合は外接円
- →これが他の点も包含する場合、それ以上大きくする必要は無い
- 最小包含円は、任意の3点も当然包含せねばならない
- →それより小さくならない
よって、3点の組み合わせを列挙して、以下の計算を行えばよい。
- 3点が鋭角か鈍角か判定
- 3辺の長さを計算し、短い順に $a,b,c$ とする
- $a^2+b^2 \le c^2$ なら直角または鈍角、逆なら鋭角
- 直角または鈍角三角形なら、3点の最小包含円は、辺 $c$ の中点を中心とした半径 $c/2$ の円
- 鋭角三角形なら、外接円
- 外接円 を参考に、外心と半径を計算
- 求めた中心から、全ての点が半径以内にあるか確認
- この時、演算誤差によっては判定から漏れる場合もあるため、半径には微小値を足しておく
- 条件を満たす円が見つかったら終了
計算量は全部で $O(N^4)$ となるが、途中で見つかったら打ち切ることができる。
全ての3点について最小包含円を求め、その半径の最大値を取るのでもよい（$O(N^3)$）。
以下の方法では、乱択ではあるがより高速に求められるっぽい。
import sys
from itertools import combinations
import numpy as np
n = int(input())
points = np.array([list(map(int, line.split())) for line in sys.stdin], dtype=np.float64)
if n == 2:
p1, p2 = points
print(np.sqrt(((p1 - p2) ** 2).sum()) / 2)
exit()
ans = 10 ** 18
for p1, p2, p3 in combinations(points, 3):
A = ((p2 - p3) ** 2).sum()
B = ((p3 - p1) ** 2).sum()
C = ((p1 - p2) ** 2).sum()
sa, sb, sc = sorted([A, B, C])
if sa + sb <= sc + 1e-7:
c = (p2 + p3 if A == sc else p1 + p3 if B == sc else p1 + p2) / 2
R2 = sc / 4
else:
T = A * (B + C - A)
U = B * (C + A - B)
W = C * (A + B - C)
c = (T * p1 + U * p2 + W * p3) / (T + U + W)
R2 = ((c - p1) ** 2).sum()
if ((points - c) ** 2).sum(axis=1).max() <= R2 + 1e-7:
print(np.sqrt(R2))
break
else:
raise AssertionError
