結果
| 問題 |
No.5016 Worst Mayor
|
| コンテスト | |
| ユーザー |
 ra5anchor
|
| 提出日時 | 2025-04-30 04:15:44 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,435 ms / 2,000 ms |
| コード長 | 11,620 bytes |
| コンパイル時間 | 426 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 111,160 KB |
| スコア | 25,846,839,270 |
| 平均クエリ数 | 400.00 |
| 最終ジャッジ日時 | 2025-04-30 04:17:04 |
| 合計ジャッジ時間 | 73,559 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / 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 TimeKeeper:
def __init__(self):
self.start_time = perf_counter()
def is_time_over(self, LIMIT):
return (perf_counter() - self.start_time) >= LIMIT
def time_now(self):
return (perf_counter() - self.start_time)
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)
# self.no_more_road = False
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 choose_action(self, type):
if self.collaborators < 65:
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 type[0] == "0":
for p0 in [6]:
path = []
r, c = 0, p0
path.append((r, c))
while r < H-1:
if (len(path)+1)%2==1:
r += 1
elif (len(path)+1)%4==0:
c -= 1
elif (len(path)+1)%4==2:
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[2] == "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])))
road.extend(edges)
if type[1] == "0":
ps = [2, 10]
elif type[1] == "1":
ps = [10, 2]
for p0 in ps:
path = []
r, c = p0, 0
path.append((r, c))
while c < H-1:
if (len(path)+1)%2==1:
c += 1
elif (len(path)+1)%4==0:
r -= 1
elif (len(path)+1)%4==2:
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[2] == "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])))
road.extend(edges)
elif type[0] == "1":
for p0 in [6]:
path = []
r, c = p0, 0
path.append((r, c))
while c < H-1:
if (len(path)+1)%2==1:
c += 1
elif (len(path)+1)%4==0:
r -= 1
elif (len(path)+1)%4==2:
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[2] == "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])))
road.extend(edges)
if type[1] == "0":
ps = [2, 10]
elif type[1] == "1":
ps = [10, 2]
for p0 in ps:
path = []
r, c = 0, p0
path.append((r, c))
while r < H-1:
if (len(path)+1)%2==1:
r += 1
elif (len(path)+1)%4==0:
c -= 1
elif (len(path)+1)%4==2:
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[2] == "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])))
road.extend(edges)
#! 順番を保ったまま重複を除去
road = list(dict.fromkeys(road))
# print(road, file=sys.stderr)
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, tk, LIMIT, type, 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(type)
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)
tk = TimeKeeper()
LIMIT = 0.8
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])
best_sc = 0
for type in ["000","010","100","110","001","011","101","111"]:
solver = Solver(N, T, citizens, DEBUG)
ans, sc = solver.solve(tk, LIMIT, type, simu=True)
print(f"{type=} {sc=}", file=sys.stderr)
if sc > best_sc:
best_sc = sc
best_type = type
solver = Solver(N, T, citizens, DEBUG)
ans, sc = solver.solve(tk, LIMIT, best_type, 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)