Loading [MathJax]/extensions/TeX/mathchoice.js
Action disabled: index
[[AtCoder Beginner Contest 151 D～F問題メモ]]
現在位置: トップページ » アルゴリズム » contest_history » 索引 » 2020 » AtCoder Beginner Contest 151 D～F問題メモ

−目次

AtCoder Beginner Contest 151 D～F問題メモ

AtCoder Beginner Contest 151

D - Maze Master

D - Maze Master

問題

  • '.' と '#' からなる H×W のフィールドが与えられる
    • '.' は道、'#' は壁で通れない
    • 道は2マス以上あり、全ての道は互いに繋がっている
  • 道の中からスタートとゴールを決め、上下左右へ隣接する道への移動を距離1として、スタートからゴールまで最短距離で移動する
  • スタートとゴールを適切に決めたとき、移動距離の最大値を求めよ
  • 1≤H,W≤20

解法

幅優先探索。

スタートが決められたとき、そこから最も遠いマスは、幅優先探索で最後に訪れたマスとなる。

よって、道である各マスをスタート地点として全て試し、最長移動距離の最大値が答え。

H,W の上限が小さいので、スタート地点候補が最大400、1回の探索で探索するマスが最大400、あわせて160000回に比例する計算量で間に合う。

なお、木の直径を求めるように「適当な1マスから最遠点を求める」→「そこからの最遠点を求める」方法だと、ループがある場合は最適が保証されない。 たとえば以下の感じ。 

.....  (1,1)からスタートすると、最遠点は(4,4)
.##.#  →そこからの最遠点は(1,1)
.##.#
....#  しかし実際は、(1,5),(4,1) の組が最遠

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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

E - Max-Min Sums

問題

  • 整数集合 X に対し f(X)=maxX−minX と定義する
  • N 個の整数 A1,...,AN が与えられる
  • ここから K 個を選び、それらからなる集合を S とする
    • 同じ値であっても添字が異なる要素を区別すると、そのような選び方は NCK 通りある
  • 全ての選び方についての 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 も、大小を逆に考えればよい。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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

programming_algorithm/contest_history/atcoder/2020/0112_abc151.txt · 最終更新: by ikatakos
文書の先頭へ
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0