結果
| 問題 | No.5016 Worst Mayor |
| ユーザー |
 ra5anchor
|
| 提出日時 | 2025-04-29 20:54:34 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,873 bytes |
| コンパイル時間 | 460 ms |
| コンパイル使用メモリ | 82,112 KB |
| 実行使用メモリ | 91,092 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2025-04-29 20:54:43 |
| 合計ジャッジ時間 | 7,863 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 49 |
ソースコード
import copy
import random
from time import perf_counter
import argparse
import sys
import math
import heapq
from heapq import heapify, heappop, heappush
# --- Constants ---
GRID_SIZE = 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
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()
# {((r1, c1), (r2, c2)), ...} 頂点順はソートしておく
self.day = 0
self.actions = []
self.daily_revenue = 0
def execute_action(self, action):
action_type = action[0]
if action_type == 1: # 道路建設
r1, c1, r2, c2 = action[1:]
cost = int(HIGHWAY_BUILD_BASE_COST / (self.collaborators**0.5))
if self.money >= cost:
self.money -= cost
coord1 = (r1, c1)
coord2 = (r2, c2)
if coord1 > coord2:
coord1, coord2 = coord2, coord1
self.highways.add((coord1, coord2))
else:
print(f"ERROR no money: {action=}")
exit()
elif action_type == 2: # 協力者集め
self.collaborators += 1
elif action_type == 3: # 資金集め
self.money += FUNDRAISE_AMOUNT
return
def update_daily_revenue(self, current_highways):
# 収益の更新
# O(N*(V+E)logV) = 2*10**6くらい?
total_highway_segments_used = 0
graph = self.build_graph(current_highways)
for k in range(self.N):
start_node = (self.citizens[k][0], self.citizens[k][1])
end_node = (self.citizens[k][2], self.citizens[k][3])
# 家から会社への最短経路での高速道路利用数を計算
distance, path_highway_segments = self.get_shortest_path_info(start_node, end_node, graph, current_highways)
total_highway_segments_used += path_highway_segments
# 更新
self.daily_revenue = 2 * HIGHWAY_REVENUE * total_highway_segments_used # 往復するので2倍
return
def build_graph(self, current_highways):
# グリッドと高速道路情報から、最短経路計算用のグラフ表現を作る
graph = dict()
for r in range(GRID_SIZE):
for c in range(GRID_SIZE):
node = (r, c)
graph[node] = []
# 隣接ノードへのエッジを追加
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < GRID_SIZE and 0 <= nc < GRID_SIZE:
neighbor = (nr, nc)
# エッジの重みを決定 (高速道路かどうか)
coord1 = tuple(sorted((node, neighbor))) # set に登録する形式に合わせる
weight = HIGHWAY_COST if coord1 in current_highways else NORMAL_COST
graph[node].append((neighbor, weight))
return graph
def get_shortest_path_info(self, start_node, end_node, graph, current_highways):
# 最短経路と高速道路使用本数を計算
distances = {node: 10**18 for node in graph}
highway_counts = {node: 0 for node in graph}
visited = set()
# (distance, highway_count, current_node) を優先度付きキューに入れる
pq = []
heappush(pq, (0.0, 0, start_node))
distances[start_node] = 0.0
while pq:
dist, hw_count, current_node = heappop(pq)
if current_node in visited:
continue
visited.add(current_node)
if current_node == end_node:
return distances[end_node], highway_counts[end_node]
for neighbor, weight in graph[current_node]:
new_dist = dist + weight
edge_coords = tuple(sorted((current_node, neighbor)))
is_highway = edge_coords in current_highways
new_hw_count = hw_count + (1 if is_highway else 0)
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
highway_counts[neighbor] = new_hw_count
heappush(pq, (new_dist, new_hw_count, neighbor))
return None, 0
def choose_action(self):
# TODO: 最適な行動を選択するロジックを実装する
# 1. 高速道路建設
# 2. 協力者集め
# 3. 資金集め
# action = [1, i1, j1, i2, j2]
# action = [2]
if self.collaborators < 100:
action = [2]
elif self.day >= 350:
action = [3]
else:
cost = int(10**7 / self.collaborators ** 0.5)
if self.money < cost:
action = [3]
else:
action = [1]
while True:
direction = random.randrange(2)
if direction == 0: # yoko
i = random.randrange(14)
j = random.randrange(13)
a, b, c, d = (i, j, i, j+1)
else:
i = random.randrange(13)
j = random.randrange(14)
a, b, c, d = (i, j, i+1, j)
if ((a, b), (c, d)) not in self.highways:
action.extend([a, b, c, d])
break
return action
def solve(self, tk, LIMIT):
# --- シミュレーションループ ---
for day in range(self.T):
self.day = day
if self.DEBUG == False:
M, C = map(int, input().split())
self.money = M
self.collaborators = C
# 1. 行動選択フェーズ
action = self.choose_action()
self.actions.append(action) # 行動を記録
# 2. 行動実行フェーズ
self.execute_action(action)
# 道路建設した場合は収益を更新
if self.DEBUG == True and action[0] == 1:
self.update_daily_revenue(self.highways)
# 3. 収益計算フェーズ
self.money += self.daily_revenue
print(f"{day=} {action=} {self.money=} {self.collaborators=} highways={len(self.highways)} {self.daily_revenue=}", file=sys.stderr)
return self.actions, self.money
###########################################
def main(DEBUG):
tk = TimeKeeper()
LIMIT = 0.8
N, T = map(int, input().split()) # N=3000, T=400 で固定
citizens = []
for _ in range(N):
a, b, c, d = map(int, input().split())
citizens.append([a-1, b-1, c-1, d-1])
solver = Solver(N, T, citizens, DEBUG)
ans, sc = solver.solve(tk, LIMIT)
for action in ans:
if action[0] == 1:
a, b, c, d = action[1:]
print(1, a+1, b+1, c+1, d+1)
else:
print(*action)
print("SC", sc, file=sys.stderr)
return
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)