結果

問題 No.5019 Hakai Project
ユーザー Kiri8128Kiri8128
提出日時 2023-11-19 08:57:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,178 ms / 3,000 ms
コード長 20,483 bytes
コンパイル時間 422 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 271,504 KB
スコア 2,848,956,807
最終ジャッジ日時 2023-11-19 08:59:33
合計ジャッジ時間 101,167 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,868 ms
268,280 KB
testcase_01 AC 2,017 ms
262,432 KB
testcase_02 AC 2,115 ms
271,184 KB
testcase_03 AC 1,706 ms
237,608 KB
testcase_04 AC 1,819 ms
253,716 KB
testcase_05 AC 1,960 ms
270,900 KB
testcase_06 AC 1,892 ms
263,168 KB
testcase_07 AC 1,903 ms
267,212 KB
testcase_08 AC 1,886 ms
261,232 KB
testcase_09 AC 2,178 ms
271,504 KB
testcase_10 AC 1,704 ms
244,736 KB
testcase_11 AC 2,016 ms
268,016 KB
testcase_12 AC 1,833 ms
252,864 KB
testcase_13 AC 1,996 ms
270,348 KB
testcase_14 AC 1,788 ms
257,672 KB
testcase_15 AC 1,830 ms
257,312 KB
testcase_16 AC 1,757 ms
231,012 KB
testcase_17 AC 1,654 ms
251,416 KB
testcase_18 AC 1,933 ms
270,656 KB
testcase_19 AC 1,958 ms
269,204 KB
testcase_20 AC 1,783 ms
219,132 KB
testcase_21 AC 1,806 ms
240,168 KB
testcase_22 AC 1,827 ms
265,436 KB
testcase_23 AC 2,023 ms
269,760 KB
testcase_24 AC 2,010 ms
268,860 KB
testcase_25 AC 1,926 ms
265,868 KB
testcase_26 AC 1,940 ms
266,392 KB
testcase_27 AC 1,850 ms
268,360 KB
testcase_28 AC 1,879 ms
255,392 KB
testcase_29 AC 1,934 ms
271,296 KB
testcase_30 AC 1,782 ms
230,644 KB
testcase_31 AC 1,905 ms
247,460 KB
testcase_32 AC 1,942 ms
260,284 KB
testcase_33 AC 1,768 ms
260,736 KB
testcase_34 AC 1,781 ms
230,512 KB
testcase_35 AC 1,846 ms
244,364 KB
testcase_36 AC 1,656 ms
220,892 KB
testcase_37 AC 2,015 ms
270,740 KB
testcase_38 AC 1,563 ms
192,452 KB
testcase_39 AC 1,962 ms
269,236 KB
testcase_40 AC 1,868 ms
240,636 KB
testcase_41 AC 1,957 ms
271,096 KB
testcase_42 AC 1,813 ms
256,576 KB
testcase_43 AC 1,844 ms
263,120 KB
testcase_44 AC 1,779 ms
224,948 KB
testcase_45 AC 1,644 ms
236,952 KB
testcase_46 AC 1,790 ms
248,140 KB
testcase_47 AC 1,755 ms
218,100 KB
testcase_48 AC 1,936 ms
250,248 KB
testcase_49 AC 1,801 ms
222,212 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

from time import time
from heapq import heapify, heappush as hpush, heappop as hpop
def dijkstra(i0, j0, target_i = None, target_j = None):
    ij0 = i0 * N + j0
    if target_i is None:
        if DEBUG:
            print("Dijkstra", i0, j0)
    else:
        target_ij = target_i * N + target_j
        if DEBUG:
            print("Dijkstra", i0, j0, target_i, target_j)
    n = N * N
    kk = 18
    mm = (1 << kk) - 1
    h = [ij0]
    D = [-1] * n
    done = [0] * n
    D[ij0] = 0
    while h:
        x = hpop(h)
        d, ij = x >> kk, x & mm
        if done[ij]: continue
        done[ij] = 1
        i, j = ij // N, ij % N
        # for nij, w in E[ij]:
        for ni, nj in ((i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)):
            if 0 <= ni < N and 0 <= nj < N:
                nij = ni * N + nj
                w = 1 if A[ni][nj] in (".", "X") else 2
                nd = d + w
                if D[nij] < 0 or D[nij] > nd:
                    if done[nij] == 0:
                        hpush(h, (nd << kk) + nij)
                        D[nij] = nd
    if 0 and DEBUG:
        print("Dijkstra")
        print("D =", D)
    if target_i is None:
        return D
    ij = target_ij
    L = []
    while 1:
        i, j = ij // N, ij % N
        L.append((i, j))
        if not D[ij]:
            break
        for pi, pj in ((i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)):
            if 0 <= pi < N and 0 <= pj < N:
                pij = pi * N + pj
                w = 1 if A[i][j] in (".", "X") else 2
                if D[pij] == D[ij] - w:
                    ij = pij
                    break
    return L[::-1]

def move(target_i, target_j):
    global cost
    global ANS
    global current_i, current_j
    if DEBUG:
        print("DIJK ->", dijkstra(current_i, current_j, target_i, target_j))
    
    b = sum(B)
    path = dijkstra(current_i, current_j, target_i, target_j)
    for (i, j), (ni, nj) in zip(path, path[1:]):
        if ni > i:
            ANS.append((1, "D"))
        elif ni < i:
            ANS.append((1, "U"))
        elif nj > j:
            ANS.append((1, "R"))
        elif nj < j:
            ANS.append((1, "L"))
        else:
            assert 0
        cost += (1 if A[ni][nj] in (".", "X") else 2) * (b + 1) ** 2
    
    current_i = target_i
    current_j = target_j
    
    if 0:
        while (current_i, current_j) != (target_i, target_j):
            if current_i < target_i:
                ANS.append((1, "D"))
                current_i += 1
            elif current_i > target_i:
                ANS.append((1, "U"))
                current_i -= 1
            elif current_j < target_j:
                ANS.append((1, "R"))
                current_j += 1
            elif current_j > target_j:
                ANS.append((1, "L"))
                current_j -= 1
            cost += (1 if A[current_i][current_j] in (".", "X") else 2) * (b + 1) ** 2
    if DEBUG:
        print("Move to", (target_i, target_j), "cost =", cost)

def buy(k):
    global cost
    assert A[current_i][current_j] == "@"
    cost += price[k]
    B[k] += 1
    ANS.append((2, k + 1))
    if DEBUG:
        print("buy", k, "@", (current_i, current_j), "cost =", cost)

def bomb_check(k, ii, jj):
    s = 0
    t = 0
    for i, j in Z[k][1]:
        ni = ii + i
        nj = jj + j
        if 0 <= ni < N and 0 <= nj < N and A[ni][nj] != ".":
            if A[ni][nj] == "@":
                s += 1
            else:
                t += 1

def bomb(k):
    assert B[k] > 0
    global shop_list
    B[k] -= 1
    ANS.append((3, k + 1))
    for i, j in Z[k][1]:
        ni = current_i + i
        nj = current_j + j
        if 0 <= ni < N and 0 <= nj < N and A[ni][nj] != ".":
            
            if A[ni][nj] == "@":
                pass # shop_list.destroyed
            A[ni][nj] = "X"
    if DEBUG:
        print("bomb", k, "@", (current_i, current_j), "cost =", cost)

def answer():
    if not LOCAL:
        print(len(ANS))
        for a, b in ANS:
            print(a, b)
    
    if DEBUG:
        print("cost =", cost)
        writetext_output(ANS)

def disp():
    if DEBUG:
        print("")
        print("-" * 20)
        print("price =", price)
        print("inv   =", price_inv)
        print("power =", power)
        
        building_cnt = sum(a.count("#") for a in A)
        shop_cnt = sum(a.count("@") for a in A)
        score = 1 if building_cnt else comma(10 ** 12 // (10 ** 4 + cost))
        print("building cnt =", building_cnt)
        print("shop cnt =", shop_cnt)
        print("shop_list =", len(shop_list), shop_list)
        print("cost =", cost)
        print("score =", score)
        print("A =")
        for a in A:
            print("".join(a))
        print("-" * 20)
        print("cost =", cost)
        print("score =", score)
        print("")
def moving_cost_factor():
    return 6

def best_shop(i, j):
    best_i = -1
    best_j = -1
    best = 1000
    for ti, tj in shop_list:
        d = abs(ti - i) + abs(tj - j)
        if 0:
            d += (max(10 - ti, 0) + max(ti - 39, 0) + max(10 - tj, 0) + max(tj - 39, 0)) * moving_cost_factor()
            if 21 <= ti < 29:
                d += 15
            if 21 <= tj < 29:
                d += 15
        if d < best:
            best = d
            best_i = ti
            best_j = tj
    return best_i, best_j

def calc_favorite_shops():
    L = []
    # for ti, tj in ((9, 9), (9, 40), (40, 40), (40, 9)):
    # for ti, tj in ((9, 9), (9, 24), (9, 40), (24, 40), (40, 40), (40, 24), (40, 9)):
    for ti, tj in ((9, 9), (9, 24), (9, 40), (24, 40), (40, 40), (40, 24), (40, 9), (24, 9)):
    # for ti, tj in ((7, 7), (7, 24), (7, 42), (24, 42), (42, 42), (42, 24), (42, 7), (24, 7)):
    # for ti, tj in ((10, 10), (10, 24), (10, 41), (24, 41), (41, 41), (41, 24), (41, 10), (24, 10)):
    # for ti, tj in ((9, 9), (9, 24), (9, 40), (24, 40), (40, 40), (40, 24), (40, 9), (24, 9), (24, 24)):
    # for ti, tj in ((9, 9), (7, 24), (9, 40), (24, 42), (40, 40), (42, 24), (40, 9), (24, 7)):
    # for ti, tj in ((9, 9), (9, 20), (9, 30), (9, 40), (20, 40), (30, 40), (40, 40), (40, 30), (40, 20), (40, 9), (30, 9), (20, 9)):
        best = 10 ** 10
        best_k = -1
        for k, (i, j) in enumerate(shop_list):
            d = (ti - i) ** 2 + (tj - j) ** 2
            if d < best:
                best = d
                best_k = k
        if best_k not in L:
            L.append(best_k)
    return L
def calc_weight(shops):
    W = [[1.0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in shops:
                si, sj = shop_list[k]
                d = max(abs(i - si), abs(j - sj))
                if d <= 20:
                    for ss in (0.2, 0.6, 1.0):
                        w = 1 / (1 + d * ss)
                        W[i][j] *= (1 - w)
    for i in range(N):
        for j in range(N):
            W[i][j] = int(10 ** 4 * W[i][j]) + 1
    
    return W
def find_best_cand_stay():
    best = 0
    best_cand = None
    for b, i, j, v in candidates_stay:
        k = favorite_shops[v]
        ev = 0
        si, sj = shop_list[k]
        for bi, bj in position[b]:
            ni = si + bi
            nj = sj + bj
            if 0 <= ni < N and 0 <= nj < N:
                if cover_count_stay[ni][nj] == 0:
                    ev += weight[ni][nj]
        ev *= price_inv[b]
        if ev > best:
            best = ev
            best_cand = (b, i, j, v, ev)
    if DEBUG:
        if best_cand is not None:
            print("Best Cand Stay =", best_cand, int(best / 10 ** 6 + 0.5))
        
    return best_cand

def calc_candidates_stay():
    # 基地からの攻撃候補
    candidates_stay = []
    for v, k in enumerate(favorite_shops):
        si, sj = shop_list[k]
        for b in range(M):
            for bi, bj in position[b]:
                ni = si + bi
                nj = sj + bj
                if (bi or bj) and 0 <= ni < N and 0 <= nj < N and favorite_shops_flg[ni][nj] > v:
                    break
            else:
                candidates_stay.append((b, si, sj, v))
    return candidates_stay

def calc_candidates_away():
    candidates_away = []
    candidates_efficiency = []
    candidates_matrix = [[[] for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for b in range(M):
                mav = -1
                for v, k in enumerate(favorite_shops):
                    si, sj = shop_list[k]
                    di, dj = si - i, sj - j
                    if -20 <= di <= 20 and -20 <= dj <= 20 and position_matrix[b][di][dj]:
                        if di or dj:
                            # ぴったり動いていない場合は Stay に入れれば良いので OK
                            mav = max(mav, v)

                best = 10 ** 9
                best_v = None
                for v in range(mav + 1, len(favorite_shops)):
                    k = favorite_shops[v]
                    si, sj = shop_list[k]
                    d = abs(i - si) + abs(j - sj)
                    if d <= best:
                        best = d
                        best_v = v

                if best_v is None:
                    continue
                v = best_v
                k = favorite_shops[v]
                si, sj = shop_list[k]
                if v < len(favorite_shops):
                    u = len(candidates_away)
                    candidates_away.append((b, i, j, v))
                    benefit = 0
                    for bi, bj in position[b]:
                        ni, nj = i + bi, j + bj
                        if 0 <= ni < N and 0 <= nj < N:
                            if cover_count_away[ni][nj] == 0:
                                candidates_matrix[ni][nj].append(u)
                                benefit += weight[ni][nj]
                    moving_cost = (abs(i - si) + abs(j - sj)) * moving_cost_factor()
                    efficiency = 10 ** 6 // (price[b] + moving_cost) * benefit
                    candidates_efficiency.append(efficiency)
    return candidates_away, candidates_efficiency, candidates_matrix
def find_best_cand_away():
    best = 0
    best_cand = None
    for u, (efficiency, cand) in enumerate(zip(candidates_efficiency, candidates_away)):
        if efficiency > best:
            best = efficiency
            best_cand = cand
            best_u = u
    if best_cand is None:
        return None
    b, i, j, v = best_cand
    if DEBUG:
        print("Best Cand Away =", (b, i, j, v), "Efficiency =", "{:.3f}".format(best / 10 ** 6))
    return b, i, j, v, best_u
def update_candidates_away(b, i, j, v):
    for bi, bj in position[b]:
        ni, nj = i + bi, j + bj
        if 0 <= ni < N and 0 <= nj < N and cover_count_away[ni][nj] >= 0:
            cover_count_away[ni][nj] += 1
            if cover_count_away[ni][nj] == 1:
                for u in candidates_matrix[ni][nj]:
                    _b, _i, _j, _v = candidates_away[u]
                    k = favorite_shops[_v]
                    si, sj = shop_list[k]
                    moving_cost = (abs(_i - si) + abs(_j - sj)) * moving_cost_factor()
                    candidates_efficiency[u] -= 10 ** 6 // (price[_b] + moving_cost) * weight[ni][nj]

def find_worst_cand_away():
    worst = 10 ** 18
    worst_cand = None
    for v, k in enumerate(favorite_shops):
        si, sj = shop_list[k]
        for b, i, j, u in strategy_away[v]:
            benefit = 0
            for bi, bj in position[b]:
                ni, nj = i + bi, j + bj
                if 0 <= ni < N and 0 <= nj < N:
                    if cover_count_away[ni][nj] == 1:
                        benefit += weight[ni][nj]
            moving_cost = (abs(i - si) + abs(j - sj)) * moving_cost_factor()
            efficiency = 10 ** 6 // (price[b] + moving_cost) * benefit
            if efficiency < worst:
                worst = efficiency
                worst_cand = (v, (b, i, j, u))
    return worst_cand

def remove_cand_away(v, b, i, j, u):
    if DEBUG:
        print("remove and away", (b, i, j, u))
    strategy_away[v].remove((b, i, j, u))
    for bi, bj in position[b]:
        ni, nj = i + bi, j + bj
        if 0 <= ni < N and 0 <= nj < N:
            cover_count_away[ni][nj] -= 1
            if cover_count_away[ni][nj] == 0:
                for _u in candidates_matrix[ni][nj]:
                    _b, _i, _j, _v = candidates_away[_u]
                    k = favorite_shops[_v]
                    si, sj = shop_list[k]
                    moving_cost = (abs(_i - si) + abs(_j - sj)) * moving_cost_factor()
                    candidates_efficiency[_u] += 10 ** 6 // (price[_b] + moving_cost) * weight[ni][nj]
    
    # 削除したやつの Efficiency を再計算
    k = favorite_shops[v]
    si, sj = shop_list[k]
    benefit = 0
    for bi, bj in position[b]:
        ni, nj = i + bi, j + bj
        if 0 <= ni < N and 0 <= nj < N:
            if cover_count_away[ni][nj] == 0:
                candidates_matrix[ni][nj].append(u)
                benefit += weight[ni][nj]
    moving_cost = (abs(i - si) + abs(j - sj)) * moving_cost_factor()
    efficiency = 10 ** 6 // (price[b] + moving_cost) * benefit
    candidates_efficiency[u] = efficiency

try:
    LOCAL
except NameError:
    LOCAL = 0

loop = 1
if LOCAL:
    DEBUG = 1
    # N, M, A, Z = random_testcase()
    print("Seed ?")
    I = input()
    if int(I) < 0:
        loop = -int(I)
        DEBUG = 0
    else:
        N, M, A, Z = preset_testcase(int(I))
else:
    DEBUG = 0
    N, M = map(int, input().split())
    A = []
    for _ in range(N):
        A.append([a for a in input()])
    Z = []
    for _ in range(M):
        C, L = map(int, input().split())
        pos = []
        for _ in range(L):
            a, b = map(int, input().split())
            pos.append((a, b))
        Z.append((C, pos))

score_sum = 0
for lp in range(loop):
    sTime = time()
    target_time = 2.5 * (3 if LOCAL else 1)
    if loop > 1:
        N, M, A, Z = preset_testcase(lp)
    cover_count_stay = [[-1 if aa == "." else 0 for aa in a] for a in A]
    if DEBUG:
        writetext_input(N, M, A, Z)
    price = []
    price_inv = []
    power = []
    position = []
    position_matrix = []
    B = [0] * M
    cost = 0
    current_i = 0
    current_j = 0
    ANS = []
    if DEBUG:
        print("N =", N)
        print("M =", M)
    shop_list = []
    for i, a in enumerate(A):
        for j, aa in enumerate(a):
            if aa == "@":
                shop_list.append((i, j))
    shop_list_destroyed = [0] * len(shop_list)

    disp()
    for C, pos in Z:
        if 0 and DEBUG:
            print("C, cnt =", C, len(pos), "{:.4f}".format(len(pos) / C))
            print("pos =", pos)
        price.append(C)
        price_inv.append(10 ** 6 // C)
        power.append(len(pos))
        position.append(pos)
        if 0:
            print("")
            print("C =", C)
            print("cnt =", len(pos))

        z = [[0] * 41 for _ in range(41)]
        for i, j in pos:
            z[i][j] = 1
        position_matrix.append(z)
        if 0:
            print("pos =")
            for zz in z:
                print("".join(zz))
    original_building_cnt = sum(a.count("#") for a in A)
    original_shop_cnt = sum(a.count("@") for a in A)


    # 基地とする店(お気に入りショップ)を選ぶ
    favorite_shops = calc_favorite_shops()
    if DEBUG:
        if 0:
            print("position =")
            for b, _pos in enumerate(position):
                print(b, _pos)
        print("favorite_shops =", favorite_shops)
    weight = calc_weight(favorite_shops)
    if DEBUG and 0:
        print("weight =")
        for w in weight:
            print(w)

    favorite_shops_flg = [[-1] * N for _ in range(N)]
    for v, k in enumerate(favorite_shops):
        si, sj = shop_list[k]
        favorite_shops_flg[si][sj] = v

    # Stay(基地にいながら)攻撃の候補・戦略
    # まずは上位から適当に使って破壊(ある程度破壊しておくと後半の計算時間を節約できる)
    candidates_stay = calc_candidates_stay()
    strategy_stay = [[] for _ in range(len(favorite_shops))]
    while 1:
        b, i, j, v, ev = find_best_cand_stay()
        if ev < 500 * 10 ** 6:
            break
        k = favorite_shops[v]
        strategy_stay[v].append((b, i, j, None))
        si, sj = shop_list[k]
        for bi, bj in position[b]:
            ni = si + bi
            nj = sj + bj
            if 0 <= ni < N and 0 <= nj < N:
                if cover_count_stay[ni][nj] >= 0:
                    cover_count_stay[ni][nj] += 1

    if DEBUG and 0:
        print("candidates_stay =", candidates_stay)
    if DEBUG:
        print("strategy_stay =")
        for v in range(len(strategy_stay)):
            print(v, strategy_stay[v])

    # Away(基地から離れて)攻撃の候補・戦略
    # 実装の都合で、基地にいるものも含めている
    cover_count_away = [[0 if aa == 0 else -1 for aa in a] for a in cover_count_stay]
    candidates_away, candidates_efficiency, candidates_matrix = calc_candidates_away()

    strategy_away = [[] for _ in range(len(favorite_shops))]
    while 1:
        cand = find_best_cand_away()
        if cand is None:
            if 0 and time() - sTime < target_time:
                for _ in range(5):
                    v, (b, i, j, u) = find_worst_cand_away()
                    remove_cand_away(v, b, i, j, u)
                    # strategy_away[v].remove((b, i, j, u))
                    if DEBUG:
                        print("REMOVE Successful", (b, i, j, u))
                continue
            break
        b, i, j, v, u = cand

        update_candidates_away(b, i, j, v)
        strategy_away[v].append((b, i, j, u))
    
    
    if DEBUG:
        print("strategy_away")
        for v, s in enumerate(strategy_away):
            print(v, s)
    
    # ソート用
    def f(x, si, sj):
        b, i, j, u = x
        return (si - i) ** 2 + (sj - j) ** 2
    
    def cheapest(strategy):
        D0 = dijkstra(current_i, current_j)
        best = 10 ** 18
        for b, i, j, u in strategy:
            D = dijkstra(i, j)
            for k, (si, sj) in enumerate(shop_list):
                if A[si][sj] == "@":
                    sij = si * N + sj
                    cost = D0[sij] + D[sij] * 4
                    if cost < best:
                        best = cost
                        best_strategy = (b, i, j, u)
                        best_k = k
        b, i, j, u = best_strategy
        k = best_k
        return (b, i, j, u, k)
    
    # 戦略に基づいてシミュレーション
    for v, k in enumerate(favorite_shops):
        si, sj = shop_list[k]
        
        # Away に入れた Stay 分を戻す(一旦逆ソートしている)
        strategy_away[v].sort(key = lambda x: -f(x, si, sj))
        while strategy_away[v]:
            b, i, j, u = strategy_away[v][-1]
            if (i, j) == (si, sj):
                strategy_stay[v].append(strategy_away[v].pop())
            else:
                break
        
        while strategy_away[v]:
            (b, i, j, u, k) = cheapest(strategy_away[v])
            si, sj = shop_list[k]
            move(si, sj)
            buy(b)
            move(i, j)
            bomb(b)
            strategy_away[v].remove((b, i, j, u))
        
        if 0:
            # 近い方から順に使う
            strategy_away[v].sort(key = lambda x: f(x, si, sj))
            for b, i, j, u in strategy_away[v]:
                move(si, sj)
                buy(b)
                move(i, j)
                bomb(b)

        move(si, sj)
        for b, i, j, u in strategy_stay[v]:
            move(i, j)
            buy(b)
        for b, i, j, u in strategy_stay[v]:
            bomb(b)
    
    if loop == 1:
        answer()
        disp()
    else:
        building_cnt = sum(a.count("#") for a in A)
        shop_cnt = sum(a.count("@") for a in A)
        score = 1 if building_cnt else 10 ** 12 // (10 ** 4 + cost)
        score_sum += score
        average_score = int(score_sum / (lp + 1) + 0.5)
        average_cost = int(10 ** 12 / average_score - 10000 + 0.5)
        print("lp =", lp, "cost =", cost, "score =", comma(score // 1000) + "K", (original_building_cnt, original_shop_cnt), "average =", average_cost, comma(int(average_score) // 1000) + "K")
if loop > 1:
    print("END")
0