AtCoder Beginner Contest 151

やっとratedになったが、誤答が多かった（テストコードにいくつかのprint()があって、削除を忘れた)から今回の成績が良くなかった…

C - Welcome to AtCoder

要するにac_listを保存する。

import sys
readline = sys.stdin.buffer.readline

n, m = map(int, readline().split())
ac_lst = [False] * (n + 1)
wa_lst = [0] * (n + 1)
ac = w = 0
for _ in range(m):
    a, b = readline().split()
    a = int(a)
    if ac_lst[a]:
        continue
    if b == b'WA':  # sys.stdin.readlineなら'WA'で十分
        wa_lst[a] += 1
    else:
        ac += 1
        w += wa_lst[a]
        ac_lst[a] = True
print(ac, w)

D - Maze Master

PAST1 - J - 地ならし
と殆ど同じです。
ちなみに今回ではheapqがdequeより遅かった。

import sys
from heapq import heappop, heappush
readline = sys.stdin.readline


H, W = map(int, readline().split())
grid = '#' * (W + 2) + ''.join('#' + readline().strip() +
                               '#' for _ in range(H)) + '#' * (W + 2)
INF = 400


def shortest(grid, start, cost=0):
    dist = [INF] * (H + 2) * (W + 2)
    move = (-1, 1, W + 2, -W - 2)
    st = [start]
    dist[start] = 0
    while(st):
        sx = heappop(st)
        c = dist[sx]
        for a in move:
            x = sx + a
            if grid[x] == '#':
                continue
            dx = dist[sx] + 1
            if dist[x] <= dx:
                continue
            dist[x] = dx
            heappush(st, x)
    return max(x for x in dist if x < INF)


m = 0
for i in range(W + 3, (H + 1) * (W + 2) - 1):
    if grid[i] == '#':
        continue
    tm = shortest(grid, i)
    if m < tm:
        m = tm
print(m)

deque:

import sys
from collections import deque
readline = sys.stdin.readline


H, W = map(int, readline().split())
grid = '#' * (W + 2) + ''.join('#' + readline().strip() +
                               '#' for _ in range(H)) + '#' * (W + 2)
INF = 400


def shortest(grid, start, cost=0):
    dist = [INF] * (H + 2) * (W + 2)
    move = (-1, 1, W + 2, -W - 2)
    st = deque([start])
    dist[start] = 0
    while(st):
        sx = st.popleft()
        c = dist[sx]
        for a in move:
            x = sx + a
            if grid[x] == '#':
                continue
            dx = dist[sx] + 1
            if dist[x] <= dx:
                continue
            dist[x] = dx
            st.append(x)
    return max(x for x in dist if x < INF)


m = 0
for i in range(W + 3, (H + 1) * (W + 2) - 1):
    if grid[i] == '#':
        continue
    tm = shortest(grid, i)
    if m < tm:
        m = tm
print(m)

E - Max-Min Sums

A列が整理済みとする。(A1<=A2<=A3...)
今回の規則を見つけてみると、答えが
$\quad {\sum_k^{n}} C_{i-1}^{k-1}*(A_{i}-A_{n-i+1})$
です。
規則がわかった後、やはり間に合うため戦う。

フェルマーの小定理:
pow(x, mod-2, mod)はxのモジュラ逆数です。
$C_{i-1}^{k-1}$は、$C_{i-2}^{k-1}*(i-1)/(i-k)$で計算し、
その$1/(i-k)$はpow(i-k, mod-2, mod)で計算される。

import sys
read = sys.stdin.buffer.read
n, k, *alst = map(int, read().split())
alst.sort()
lst1 = alst[k - 1:]
lst2 = alst[n - k::-1]
mod = 10 ** 9 + 7
res = 0
prep = 1
for i in range(n - k + 1):
    res += prep * (lst1[i] - lst2[i])
    res %= mod
    prep = prep * (i + k) * pow(i + 1, mod - 2, mod)
    prep %= mod
print(res)

F - Enclose All

二つ可能な状況がある。
１、ある3点の外接円がすべて点を含む。
２、「最遠」な2点を直径の両端とする円がすべて点を含む。
テストの時、外心の計算方法は、すっかり忘れてた(笑)

from itertools import combinations
import math
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n = int(readline())
m = map(int, read().split())
points = [(x, y) for x, y in zip(m, m)]


def center(a, b, c):
    # 外心の座標と半径を計算する
    M = pow(a[0], 2) - pow(b[0], 2) + pow(a[1], 2) - pow(b[1], 2)
    N = pow(a[0], 2) - pow(c[0], 2) + pow(a[1], 2) - pow(c[1], 2)
    Yab = a[1] - b[1]
    Xab = a[0] - b[0]
    Yac = a[1] - c[1]
    Xac = a[0] - c[0]
    d = Yac * Xab - Yab * Xac
    if d == 0:  # 三点共線
        return None
    x = (M * Yac - N * Yab) / (2 * d)
    y = - (M * Xac - N * Xab) / (2 * d)
    r = math.hypot(x - a[0], y - a[1])
    return (x, y, r)


centers = []
for a, b, c in combinations(points, 3):
    cen = center(a, b, c)
    if cen is None:
        continue
    centers.append(cen)

for a, b in combinations(points, 2):  # すべて2点の直径
    cen = ((a[0] + b[0]) / 2, (a[1] + b[1]) / 2,
           math.hypot(a[0] - b[0], a[1] - b[1]) / 2)
    centers.append(cen)

res = 1000
for cx, cy, cr in centers:
    for x, y in points:
        tr = math.hypot(x - cx, y - cy)
        if tr > cr + 10e-6:
            '''
            外心との距離が半径より遠い点が外接円に含まれない。誤差のため非常に小さい値を足す
            '''
            break
    else:
        if cr < res:
            res = cr
print(res)