結果

問題 No.5019 Hakai Project
ユーザー Kiri8128Kiri8128
提出日時 2023-11-19 03:15:25
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 10,523 bytes
コンパイル時間 340 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 141,424 KB
スコア 2,490,776,865
最終ジャッジ日時 2023-11-19 03:16:08
合計ジャッジ時間 41,817 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 675 ms
107,956 KB
testcase_01 AC 730 ms
118,524 KB
testcase_02 AC 699 ms
112,388 KB
testcase_03 AC 629 ms
103,088 KB
testcase_04 AC 730 ms
116,652 KB
testcase_05 AC 709 ms
117,672 KB
testcase_06 AC 650 ms
103,008 KB
testcase_07 AC 861 ms
135,348 KB
testcase_08 AC 695 ms
119,012 KB
testcase_09 AC 753 ms
124,552 KB
testcase_10 AC 626 ms
103,416 KB
testcase_11 AC 725 ms
114,332 KB
testcase_12 AC 714 ms
127,488 KB
testcase_13 AC 669 ms
117,256 KB
testcase_14 AC 654 ms
104,340 KB
testcase_15 AC 647 ms
107,528 KB
testcase_16 RE -
testcase_17 AC 667 ms
98,196 KB
testcase_18 AC 744 ms
123,552 KB
testcase_19 AC 712 ms
107,320 KB
testcase_20 AC 739 ms
122,040 KB
testcase_21 AC 763 ms
114,880 KB
testcase_22 AC 658 ms
103,884 KB
testcase_23 AC 721 ms
115,452 KB
testcase_24 AC 841 ms
141,424 KB
testcase_25 AC 715 ms
128,624 KB
testcase_26 AC 732 ms
128,880 KB
testcase_27 AC 695 ms
111,108 KB
testcase_28 AC 668 ms
107,296 KB
testcase_29 AC 679 ms
100,612 KB
testcase_30 AC 630 ms
108,152 KB
testcase_31 AC 696 ms
120,416 KB
testcase_32 AC 630 ms
108,304 KB
testcase_33 AC 689 ms
114,172 KB
testcase_34 AC 766 ms
126,000 KB
testcase_35 AC 606 ms
101,672 KB
testcase_36 AC 679 ms
108,292 KB
testcase_37 AC 653 ms
109,480 KB
testcase_38 AC 592 ms
106,052 KB
testcase_39 AC 671 ms
102,872 KB
testcase_40 AC 715 ms
118,832 KB
testcase_41 AC 686 ms
105,500 KB
testcase_42 AC 667 ms
109,604 KB
testcase_43 AC 629 ms
99,240 KB
testcase_44 AC 699 ms
109,104 KB
testcase_45 AC 604 ms
103,852 KB
testcase_46 AC 700 ms
105,080 KB
testcase_47 AC 689 ms
115,612 KB
testcase_48 AC 733 ms
119,432 KB
testcase_49 AC 746 ms
126,460 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def move(target_i, target_j):
    global cost
    global ANS
    global current_i, current_j
    b = sum(B)
    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] == "." else 2) * (b + 1) ** 2

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

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

def answer():
    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)
        print("building cnt =", building_cnt)
        print("shop cnt =", shop_cnt)
        print("shop_list =", len(shop_list), shop_list)
        print("cost =", cost)
        print("A =")
        for a in A:
            print("".join(a))
        print("-" * 20)
        print("")

try:
    LOCAL
except NameError:
    LOCAL = 0

if LOCAL:
    DEBUG = 1
    # N, M, A, Z = random_testcase()
    N, M, A, Z = preset_testcase()
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))

AA = [a[:] for a in A]
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 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))

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)) * 5
            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)):
        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
        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():
    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 AA[ni][nj] != ".":
                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)
    return best_cand

favorite_shops = calc_favorite_shops()
if DEBUG:
    print("position =")
    for b, _pos in enumerate(position):
        print(b, _pos)
    print("favorite_shops =", favorite_shops)
weight = calc_weight(favorite_shops)
if DEBUG:
    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

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


strategy_stay = [[] for _ in range(len(favorite_shops))]
for _ in range(20):
    b, i, j, v = find_best_cand()
    k = favorite_shops[v]
    strategy_stay[v].append((b, i, j))
    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 AA[ni][nj] != ".":
            #     AA[ni][nj] = "."
            if cover_count_stay[ni][nj] >= 0:
                cover_count_stay[ni][nj] += 1

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

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 = [[[] 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]:
                    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
            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]
                efficiency = benefit * price_inv[b]
                candidates_efficiency.append(efficiency)

def find_best_cand_away():
    best = 0
    best_cand = None
    for efficiency, cand in zip(candidates_efficiency, candidates_away):
        if efficiency > best:
            best = efficiency
            best_cand = cand
    return best_cand
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:
            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]
                    candidates_efficiency[u] -= weight[ni][nj] * price_inv[_b]
            

strategy_away = [[] for _ in range(len(favorite_shops))]
while 1:
    cand = find_best_cand_away()
    if cand is None:
        break
    b, i, j, v = cand
    update_candidates_away(b, i, j, v)
    
    strategy_away[v].append((b, i, j))

if DEBUG:
    print("strategy_away")
    for v, s in enumerate(strategy_away):
        print(v, s)

for v, k in enumerate(favorite_shops):
    si, sj = shop_list[k]
    for b, i, j in strategy_away[v]:
        move(si, sj)
        buy(b)
        move(i, j)
        bomb(b)
    
    move(si, sj)
    for b, i, j in strategy_stay[v]:
        move(i, j)
        buy(b)
    for b, i, j in strategy_stay[v]:
        bomb(b)
while 0: #shop_list:
    move(*best_shop(current_i, current_j))
    ni = current_i + 1 if current_i < N - 1 else current_i - 1
    nj = current_j + 1 if current_j < N - 1 else current_j - 1
    for k in range(5):
        buy(k)
        # buy(k)
        # buy(k)
    for k in range(5):
        bomb(k)
    if 0:
        move(ni, current_j)
        for k in range(M):
            bomb(k)
        move(ni, nj)
        for k in range(M):
            bomb(k)
answer()
disp()
0