'.
' と '#
' からなる $H \times W$ のフィールドが与えられる'.
' は道、'#
' は壁で通れない幅優先探索。
スタートが決められたとき、そこから最も遠いマスは、幅優先探索で最後に訪れたマスとなる。
よって、道である各マスをスタート地点として全て試し、最長移動距離の最大値が答え。
$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)
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$ が答えに寄与するのは、$(P_i - Q_i) \times A_i$ となる。 これを全ての $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)
AtCoderでは珍しめ(?)の典型問題。 でもこういう機会でもなければ触れないし、最小包含円をさらにアレンジしてこねくり回す問題は難しくてABC向けでは無いだろうので、いい機会と言えるかも。
PythonではOpenCVを非常に使いたくなるところだが、残念ながら入っていない。
最小包含円は様々な求め方があるが、1つの解法として「与えられた点から3点を選んできて、その最小包含円のうち、その3点以外も全て包含するもの」に一致する。
よって、3点の組み合わせを列挙して、以下の計算を行えばよい。
計算量は全部で $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