# 縮小表示
from copy import deepcopy
def test_all(f):
for i, data in enumerate(eval(f'test_data{f.__name__[0]}')):
exp = data["out"]
ans = f(*deepcopy(data["in"]))
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
from itertools import accumulate
def C(N, S, W):
S = [int(s) for s in S]
W, S = zip(*sorted(zip(W, S)))
*S, = accumulate(S)
# 「全員大人」判定
ans = S[-1]
# i と i+1 の間で区切る。最後は「全員子供」判定
for i, (w, s) in enumerate(zip(W, S)):
if i != N-1 and w == W[i+1]:
continue
ans = max(ans, i+1-s + S[-1]-s)
return ans
test_all(C)
from itertools import accumulate
def C(N, S, W):
S = [int(s) for s in S]
W, S = zip(*sorted(
sorted(zip(W, S), key=lambda ws:ws[1], reverse=True),
key=lambda ws: ws[0]))
*S, = accumulate(S)
return max([i - 2*s for i, s in enumerate(S)]+[-1]) + 1 + S[-1]
test_all(C)
from collections import deque
def D(N, points):
class P():
items = []
distances = {}
@staticmethod
def get_dist(a, b):
return abs(a.x - b.x) + abs(a.y - b.y)
def __init__(self, x, y, p):
self.x = x
self.y = y
self.p = p
CLASS = self.__class__
now = len(CLASS.items)
for i, item in enumerate(CLASS.items):
d = CLASS.get_dist(self, item)
CLASS.distances[(now, i)] = d
CLASS.distances[(i, now)] = d
CLASS.items.append(self)
def __repr__(self):
return f'({self.x}, {self.y}), {self.p}'
def bfs(start, x):
q = deque([start])
visited = [start]
while len(q):
now = q.popleft()
for to in range(N):
if now != to and to not in visited and P.items[now].p * x >= P.distances[(now, to)]:
q.append(to)
visited.append(to)
return True if len(visited) == N else False
def is_connected(x):
for i in range(N):
if bfs(i, x): return True
return False
for point in points: P(*point)
ok = max(P.distances.values())
ng = -1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_connected(mid):
ok = mid
else:
ng = mid
return ok
test_all(D)
from collections import deque
from itertools import chain
def D(N, points):
class P():
items = []
distances = [[0]*N for _ in range(N)]
@staticmethod
def get_dist(a, b):
return abs(a.x - b.x) + abs(a.y - b.y)
def __init__(self, x, y, p):
self.x = x
self.y = y
self.p = p
CLASS = self.__class__
now = len(CLASS.items)
for i, item in enumerate(CLASS.items):
d = CLASS.get_dist(self, item)
CLASS.distances[now][i] = d
CLASS.distances[i][now] = d
CLASS.items.append(self)
def __repr__(self):
return f'({self.x}, {self.y}), {self.p}'
def bfs(graph, start):
q = deque([start])
visited = set([start])
while q:
now = q.popleft()
for to in graph[now]:
if to not in visited:
q.append(to)
visited.add(to)
return True if len(visited) == N else False
def is_connected(x):
graph = [[] for i in range(N)]
for i in range(N-1):
for j in range(i+1, N):
if P.items[i].p * x >= P.distances[i][j]:
graph[i].append(j)
if P.items[j].p * x >= P.distances[i][j]:
graph[j].append(i)
for i in range(N):
if bfs(graph, i): return True
return False
for point in points: P(*point)
ok = max(set(chain.from_iterable(P.distances)))
ng = -1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_connected(mid):
ok = mid
else:
ng = mid
return ok
test_all(D)
# 縮小表示
from difflib import HtmlDiff as diff
from urllib.parse import quote
tobecompared = {
"fromlines": '''
from collections import deque
def D(N, points):
class P():
items = []
distances = {}
@staticmethod
def get_dist(a, b):
return abs(a.x - b.x) + abs(a.y - b.y)
def __init__(self, x, y, p):
self.x = x
self.y = y
self.p = p
CLASS = self.__class__
now = len(CLASS.items)
for i, item in enumerate(CLASS.items):
d = CLASS.get_dist(self, item)
CLASS.distances[(now, i)] = d
CLASS.distances[(i, now)] = d
CLASS.items.append(self)
def __repr__(self):
return f'({self.x}, {self.y}), {self.p}'
def bfs(start, x):
q = deque([start])
visited = [start]
while len(q):
now = q.popleft()
for to in range(N):
if now != to and to not in visited and P.items[now].p * x >= P.distances[(now, to)]:
q.append(to)
visited.append(to)
return True if len(visited) == N else False
def is_connected(x):
for i in range(N):
if bfs(i, x): return True
return False
for point in points: P(*point)
ok = max(P.distances.values())
ng = -1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_connected(mid):
ok = mid
else:
ng = mid
return ok
'''.splitlines(),
"tolines": '''
from collections import deque
from itertools import chain
def D(N, points):
class P():
items = []
distances = [[0]*N for _ in range(N)]
@staticmethod
def get_dist(a, b):
return abs(a.x - b.x) + abs(a.y - b.y)
def __init__(self, x, y, p):
self.x = x
self.y = y
self.p = p
CLASS = self.__class__
now = len(CLASS.items)
for i, item in enumerate(CLASS.items):
d = CLASS.get_dist(self, item)
CLASS.distances[now][i] = d
CLASS.distances[i][now] = d
CLASS.items.append(self)
def __repr__(self):
return f'({self.x}, {self.y}), {self.p}'
def bfs(graph, start):
q = deque([start])
visited = set([start])
while q:
now = q.popleft()
for to in graph[now]:
if to not in visited:
q.append(to)
visited.add(to)
return True if len(visited) == N else False
def is_connected(x):
graph = [[] for i in range(N)]
for i in range(N-1):
for j in range(i+1, N):
if P.items[i].p * x >= P.distances[i][j]:
graph[i].append(j)
if P.items[j].p * x >= P.distances[i][j]:
graph[j].append(i)
for i in range(N):
if bfs(graph, i): return True
return False
for point in points: P(*point)
ok = max(set(chain.from_iterable(P.distances)))
ng = -1
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_connected(mid):
ok = mid
else:
ng = mid
return ok
'''.splitlines()}
f''''''
# 縮小表示
diff().make_file(**tobecompared)