結果

問題 No.5016 Worst Mayor
ユーザー ra5anchor
提出日時 2025-04-29 22:57:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 388 ms / 2,000 ms
コード長 6,934 bytes
コンパイル時間 665 ms
コンパイル使用メモリ 82,836 KB
実行使用メモリ 101,528 KB
スコア 16,855,558,280
平均クエリ数 400.00
最終ジャッジ日時 2025-04-29 22:57:36
合計ジャッジ時間 23,059 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)

    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):
        if self.collaborators < 50:
            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 = []
        # s = [6,7,5,8,4,9,3,10,2,11,1] # 0-10
        s = [6,7,5,8,4,9,3,10,2,11,1,12,0] # 0-12
        p0 = 4
        p1 = 8
        for i in s:
            a, b, c, d = i, p0, i+1, p0
            road.append((a, b, c, d))

        for i in s:
            a, b, c, d = p0, i, p0, i+1
            road.append((a, b, c, d))

        for i in s:
            a, b, c, d = i, p1, i+1, p1
            road.append((a, b, c, d))

        for i in s:
            a, b, c, d = p1, i, p1, i+1
            road.append((a, b, c, d))

        # for i in s:
        #     a, b, c, d = i, 6, i+1, 6
        #     road.append((a, b, c, d))

        # for i in s:
        #     a, b, c, d = 6, i, 6, i+1
        #     road.append((a, b, c, d))

        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):
        for day in range(self.T):
            self.day = day
            if not self.DEBUG:
                M, C = map(int, input().split())
                self.money, self.collaborators = M, C
            action = self.choose_action()
            self.actions.append(action)
            self.execute_action(action)
            # DEBUG モードで収益更新
            if self.DEBUG and action[0] == 1:
                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 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())
    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)

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)
0