−目次

AtCoder Beginner Contest 151 D～F問題メモ
- D - Maze Master
  - 問題
  - 解法
- E - Max-Min Sums
  - 問題
  - 解法
- F - Enclose All
  - 問題
  - 解法

AtCoder Beginner Contest 151 D～F問題メモ

AtCoder Beginner Contest 151

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)$ ）。

以下の方法では、乱択ではあるがより高速に求められるっぽい。

最小包含円 [夏季セミ2019].pptx - Google スライド

        
          
          
              
              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

            

        
      

−目次

AtCoder Beginner Contest 151 D～F問題メモ

D - Maze Master

問題

解法

E - Max-Min Sums

問題

解法

P_i,Q_iP_i,Q_i の求め方

F - Enclose All

問題

解法

$P_i,Q_i$ の求め方