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,\ldots,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,\ldots$ について、

\begin{align} f(S_1)+f(S_2)+f(S_3)+\ldots &= \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}+\ldots)-(\min{S_1}+\min{S_2}+\min{S_3}+\ldots) \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),\ldots,(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

本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
programming_algorithm/contest_history/atcoder/2020/0112_abc151.txt · 最終更新: 2020/01/12 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0