#1080942 (PyPy3) No.5016 Worst Mayor

• 問題: No.5016 Worst Mayor
• ユーザー: ra5anchor
• 提出日時: 2025-04-29 21:03:55
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 318 ms / 2,000 ms
• コード長: 7,939 bytes
• コンパイル時間: 539 ms
• コンパイル使用メモリ: 82,332 KB
• 実行使用メモリ: 100,480 KB
• スコア: 3,363,853,080
• 平均クエリ数: 400.00
• 最終ジャッジ日時: 2025-04-29 21:04:15
• 合計ジャッジ時間: 18,111 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
other	AC * 50

ソースコード

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)
            
            # 出力
            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):
    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)

    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)