やっと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)