結果
| 問題 |
No.5016 Worst Mayor
|
| ユーザー |
 ra5anchor
|
| 提出日時 | 2025-05-01 23:27:45 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,151 ms / 2,000 ms |
| コード長 | 9,478 bytes |
| コンパイル時間 | 463 ms |
| コンパイル使用メモリ | 82,332 KB |
| 実行使用メモリ | 108,476 KB |
| スコア | 26,235,764,260 |
| 平均クエリ数 | 392.00 |
| 最終ジャッジ日時 | 2025-05-01 23:28:55 |
| 合計ジャッジ時間 | 60,535 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import copy
import random
from time import perf_counter
import argparse
import sys
import math
# --- Constants ---
H = 14
INITIAL_MONEY = 10**6
INITIAL_COLLABORATORS = 1
NORMAL_COST = 1.0
HIGHWAY_COST = 0.223
HIGHWAY_REVENUE = 30
FUNDRAISE_AMOUNT = 50000
HIGHWAY_BUILD_BASE_COST = 10**7
def floyd_warshall_init(H, normal_cost):
V = H * H
INF = float('inf')
# distance and highway-count matrices
dist = [[INF] * V for _ in range(V)]
hw_count = [[0] * V for _ in range(V)]
# self-distance
for u in range(V):
dist[u][u] = 0.0
# grid adjacency
for r in range(H):
for c in range(H):
u = r * H + c
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < H and 0 <= nc < H:
v = nr * H + nc
dist[u][v] = normal_cost
# initial APSP
for k in range(V):
for i in range(V):
dik = dist[i][k]
hik = hw_count[i][k]
for j in range(V):
nd = dik + dist[k][j]
if nd < dist[i][j]:
dist[i][j] = nd
hw_count[i][j] = hik + hw_count[k][j]
return dist, hw_count
class Solver:
def __init__(self, N, T, citizens, DEBUG):
self.N = N
self.T = T
self.citizens = citizens
self.DEBUG = DEBUG
# --- 状態変数 ---
self.money = INITIAL_MONEY
self.collaborators = INITIAL_COLLABORATORS
self.highways = set()
self.day = 0
self.actions = []
self.daily_revenue = 0
# APSP 用行列の初期化
self.V = H * H
self.dist, self.hw_count = floyd_warshall_init(H, NORMAL_COST)
def update_apsp_edge(self, u, v):
# 新しい高速道路エッジ (u<->v) を反映
V = self.V
w = HIGHWAY_COST
# 直接距離更新
self.dist[u][v] = w
self.dist[v][u] = w
self.hw_count[u][v] = 1
self.hw_count[v][u] = 1
# 差分更新
for i in range(V):
di_u = self.dist[i][u]
hi_u = self.hw_count[i][u]
di_v = self.dist[i][v]
hi_v = self.hw_count[i][v]
for j in range(V):
# i -> u -> v -> j
nd = di_u + w + self.dist[v][j]
nh = hi_u + 1 + self.hw_count[v][j]
if nd < self.dist[i][j]:
self.dist[i][j] = nd
self.hw_count[i][j] = nh
# i -> v -> u -> j
nd2 = di_v + w + self.dist[u][j]
nh2 = hi_v + 1 + self.hw_count[u][j]
if nd2 < self.dist[i][j]:
self.dist[i][j] = nd2
self.hw_count[i][j] = nh2
def execute_action(self, action):
t = action[0]
if t == 1: # 道路建設
r1, c1, r2, c2 = action[1:]
cost = int(HIGHWAY_BUILD_BASE_COST / math.sqrt(self.collaborators))
if self.money >= cost:
self.money -= cost
n1 = r1 * H + c1
n2 = r2 * H + c2
edge = tuple(sorted((n1, n2)))
self.highways.add(edge)
# APSP の差分更新
self.update_apsp_edge(n1, n2)
else:
print(f"ERROR no money: {action=}")
exit()
elif t == 2: # 協力者集め
self.collaborators += 1
elif t == 3: # 資金集め
self.money += FUNDRAISE_AMOUNT
return
def update_daily_revenue(self):
# APSP の hw_count を使って収益を計算
total = 0
for a, b, c, d in self.citizens:
s = a * H + b
t = c * H + d
total += self.hw_count[s][t]
self.daily_revenue = 2 * HIGHWAY_REVENUE * total
return
def gen_edges_v(self, p0, type):
path = []
r, c = 0, p0
path.append((r, c))
for i in range(2*H-1):
if i%4==0:
c += 1
elif i%4==2:
c -= 1
else:
r += 1
path.append((r, c))
edges = []
for i in range(len(path)-1):
r0, c0 = path[i]
r1, c1 = path[i+1]
if (r0, c0) > (r1, c1):
(r0, c0), (r1, c1) = (r1, c1), (r0, c0)
if type == 1:
if c0 == c1 and c0 == p0:
c0 += 1
c1 += 1
elif c0 == c1 and c0 != p0:
c0 -= 1
c1 -= 1
edges.append((r0, c0, r1, c1))
edges.sort(key=lambda x: abs(13-(x[0]+x[2])))
return edges
def gen_edges_h(self, p0, type):
path = []
r, c = p0, 0
path.append((r, c))
for i in range(2*H-1):
if i%4==0:
r += 1
elif i%4==2:
r -= 1
else:
c += 1
path.append((r, c))
edges = []
for i in range(len(path)-1):
r0, c0 = path[i]
r1, c1 = path[i+1]
if (r0, c0) > (r1, c1):
(r0, c0), (r1, c1) = (r1, c1), (r0, c0)
if type == 1:
if r0 == r1 and r0 == p0:
r0 += 1
r1 += 1
elif r0 == r1 and r0 != p0:
r0 -= 1
r1 -= 1
edges.append((r0, c0, r1, c1))
edges.sort(key=lambda x: abs(13-(x[1]+x[3])))
return edges
def choose_action(self, types):
if self.collaborators < 60:
return [2]
if self.collaborators < 85 and len(self.highways) == 1:
return [2]
if self.day >= 300:
return [3]
cost = int(HIGHWAY_BUILD_BASE_COST / math.sqrt(self.collaborators))
if self.money < cost:
return [3]
# 道路建設
road = []
if types[0] == 0:
edges = self.gen_edges_v(6, types[2])
road.extend(edges)
if types[1] == 0:
edges = self.gen_edges_h(2, types[3])
road.extend(edges)
edges = self.gen_edges_h(10, types[4])
road.extend(edges)
elif types[1] == 1:
edges = self.gen_edges_h(10, types[3])
road.extend(edges)
edges = self.gen_edges_h(2, types[4])
road.extend(edges)
elif types[0] == 1:
edges = self.gen_edges_h(6, types[2])
road.extend(edges)
if types[1] == 0:
edges = self.gen_edges_v(2, types[3])
road.extend(edges)
edges = self.gen_edges_v(10, types[4])
road.extend(edges)
elif types[1] == 1:
edges = self.gen_edges_v(10, types[3])
road.extend(edges)
edges = self.gen_edges_v(2, types[4])
road.extend(edges)
# 順番を保ったまま重複を除去
road = list(dict.fromkeys(road))
rid = len(self.highways)
if rid >= len(road):
return [3]
else:
a, b, c, d = road[rid]
return [1, a, b, c, d]
def solve(self, types, simu):
for day in range(self.T):
self.day = day
if self.DEBUG==False and simu==False:
M, C = map(int, input().split())
self.money, self.collaborators = M, C
action = self.choose_action(types)
self.actions.append(action)
self.execute_action(action)
# 収益更新
self.update_daily_revenue()
# 収益反映
self.money += self.daily_revenue
# デバッグ出力
# print(f"day={day} action={action} money={self.money} cols={self.collaborators} highways={len(self.highways)} revenue={self.daily_revenue}", file=sys.stderr)
# 出力
if simu==False:
if action[0] == 1:
a, b, c, d = action[1:]
print(1, a+1, b+1, c+1, d+1)
else:
print(action[0])
return self.actions, self.money
def main(DEBUG):
print(f"=================", file=sys.stderr)
N, T = map(int, input().split())
citizens = []
for _ in range(N):
a, b, c, d = map(int, input().split())
citizens.append([a-1, b-1, c-1, d-1])
ntype = 5
types = [0]*ntype
solver = Solver(N, T, citizens, DEBUG)
_, sc = solver.solve(types, simu=True)
print(f"{types=} {sc=}", file=sys.stderr)
best_types = types[:]
best_sc = sc
for idx in range(ntype):
types = best_types[:]
types[idx] = 1
solver = Solver(N, T, citizens, DEBUG)
_, sc = solver.solve(types, simu=True)
print(f"{types=} {sc=}", file=sys.stderr)
if sc > best_sc:
best_sc = sc
best_types[idx] = 1
solver = Solver(N, T, citizens, DEBUG)
_, sc = solver.solve(best_types, simu=False) # 本番
print("SC", sc, file=sys.stderr)
if __name__ == '__main__':
parser = argparse.ArgumentParser(description='Debug mode')
parser.add_argument('--debug', action='store_true', help='Enable debug mode')
args = parser.parse_args()
main(args.debug)