結果
問題 | No.5019 Hakai Project |
ユーザー |
![]() |
提出日時 | 2023-11-19 19:43:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,405 ms / 3,000 ms |
コード長 | 22,350 bytes |
コンパイル時間 | 333 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 272,988 KB |
スコア | 2,862,836,239 |
最終ジャッジ日時 | 2023-11-19 19:47:39 |
合計ジャッジ時間 | 111,984 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
from time import timefrom heapq import heapify, heappush as hpush, heappop as hpopdef dijkstra(i0, j0, target_i = None, target_j = None):ij0 = i0 * N + j0if target_i is None:if DEBUG:print("Dijkstra", i0, j0)else:target_ij = target_i * N + target_jif DEBUG:print("Dijkstra", i0, j0, target_i, target_j)n = N * Nkk = 18mm = (1 << kk) - 1h = [ij0]D = [-1] * ndone = [0] * nD[ij0] = 0while h:x = hpop(h)d, ij = x >> kk, x & mmif done[ij]: continuedone[ij] = 1i, 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 + njw = 1 if A[ni][nj] in (".", "X") else 2nd = d + wif D[nij] < 0 or D[nij] > nd:if done[nij] == 0:hpush(h, (nd << kk) + nij)D[nij] = ndif 0 and DEBUG:print("Dijkstra")print("D =", D)if target_i is None:return Dij = target_ijL = []while 1:i, j = ij // N, ij % NL.append((i, j))if not D[ij]:breakfor 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 + pjw = 1 if A[i][j] in (".", "X") else 2if D[pij] == D[ij] - w:ij = pijbreakreturn L[::-1]def move(target_i, target_j):global costglobal ANSglobal current_i, current_jif 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 0cost += (1 if A[ni][nj] in (".", "X") else 2) * (b + 1) ** 2current_i = target_icurrent_j = target_jif 0:while (current_i, current_j) != (target_i, target_j):if current_i < target_i:ANS.append((1, "D"))current_i += 1elif current_i > target_i:ANS.append((1, "U"))current_i -= 1elif current_j < target_j:ANS.append((1, "R"))current_j += 1elif current_j > target_j:ANS.append((1, "L"))current_j -= 1cost += (1 if A[current_i][current_j] in (".", "X") else 2) * (b + 1) ** 2if DEBUG:print("Move to", (target_i, target_j), "cost =", cost)def buy(k):global costassert A[current_i][current_j] == "@"cost += price[k]B[k] += 1ANS.append((2, k + 1))if DEBUG:print("buy", k, "@", (current_i, current_j), "cost =", cost)def bomb_check(k, ii, jj):s = 0t = 0for i, j in Z[k][1]:ni = ii + inj = jj + jif 0 <= ni < N and 0 <= nj < N and A[ni][nj] != ".":if A[ni][nj] == "@":s += 1else:t += 1def bomb(k):assert B[k] > 0global shop_listB[k] -= 1ANS.append((3, k + 1))for i, j in Z[k][1]:ni = current_i + inj = current_j + jif 0 <= ni < N and 0 <= nj < N and A[ni][nj] != ".":if A[ni][nj] == "@":pass # shop_list.destroyedA[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 6def best_shop(i, j):best_i = -1best_j = -1best = 1000for 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 += 15if 21 <= tj < 29:d += 15if d < best:best = dbest_i = tibest_j = tjreturn best_i, best_jdef 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), (11, 24), (7, 42), (24, 38), (42, 42), (38, 24), (42, 7), (24, 11)): # 7165# for ti, tj in ((8, 8), (10, 24), (8, 41), (24, 39), (41, 41), (39, 24), (41, 8), (24, 10)):# 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)):ti, tj = tj, ti #best = 10 ** 10best_k = -1for k, (i, j) in enumerate(shop_list):d = (ti - i) ** 2 + (tj - j) ** 2if d < best:best = dbest_k = kif best_k not in L:L.append(best_k)return Ldef 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]) + 1return Wdef find_best_cand_stay():best = 0best_cand = Nonefor b, i, j, v in candidates_stay:k = favorite_shops[v]ev = 0si, sj = shop_list[k]for bi, bj in position[b]:ni = si + binj = sj + bjif 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 = evbest_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_canddef 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 + binj = sj + bjif (bi or bj) and 0 <= ni < N and 0 <= nj < N and favorite_shops_flg[ni][nj] > v:breakelse:candidates_stay.append((b, si, sj, v))return candidates_staydef 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 = -1for v, k in enumerate(favorite_shops):si, sj = shop_list[k]di, dj = si - i, sj - jif -20 <= di <= 20 and -20 <= dj <= 20 and position_matrix[b][di][dj]:if di or dj:# ぴったり動いていない場合は Stay に入れれば良いので OKmav = max(mav, v)best = 10 ** 9best_v = Nonefor 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 = dbest_v = vif best_v is None:continuev = best_vk = 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 = 0for bi, bj in position[b]:ni, nj = i + bi, j + bjif 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) * benefitcandidates_efficiency.append(efficiency)return candidates_away, candidates_efficiency, candidates_matrixdef find_best_cand_away():best = 0best_cand = Nonefor u, (efficiency, cand) in enumerate(zip(candidates_efficiency, candidates_away)):if efficiency > best:best = efficiencybest_cand = candbest_u = uif best_cand is None:return Noneb, i, j, v = best_candif DEBUG:print("Best Cand Away =", (b, i, j, v), "Efficiency =", "{:.3f}".format(best / 10 ** 6))return b, i, j, v, best_udef update_candidates_away(b, i, j, v):for bi, bj in position[b]:ni, nj = i + bi, j + bjif 0 <= ni < N and 0 <= nj < N and cover_count_away[ni][nj] >= 0:cover_count_away[ni][nj] += 1if 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 ** 18worst_cand = Nonefor v, k in enumerate(favorite_shops):si, sj = shop_list[k]for b, i, j, u in strategy_away[v]:benefit = 0for bi, bj in position[b]:ni, nj = i + bi, j + bjif 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) * benefitif efficiency < worst:worst = efficiencyworst_cand = (v, (b, i, j, u))return worst_canddef 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 + bjif 0 <= ni < N and 0 <= nj < N:cover_count_away[ni][nj] -= 1if 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 = 0for bi, bj in position[b]:ni, nj = i + bi, j + bjif 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) * benefitcandidates_efficiency[u] = efficiencytry:LOCALexcept NameError:LOCAL = 0loop = 1if LOCAL:DEBUG = 1# N, M, A, Z = random_testcase()print("Seed ?")I = input()if int(I) < 0:loop = -int(I)DEBUG = 0else:N, M, A, Z = preset_testcase(int(I))else:DEBUG = 0N, 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 = 0for lp in range(loop):sTime = time()target_time = 2.5 * (5 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] * Mcost = 0current_i = 0current_j = 0ANS = []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] = 1position_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:breakk = favorite_shops[v]strategy_stay[v].append((b, i, j, None))si, sj = shop_list[k]for bi, bj in position[b]:ni = si + binj = sj + bjif 0 <= ni < N and 0 <= nj < N:if cover_count_stay[ni][nj] >= 0:cover_count_stay[ni][nj] += 1if 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()def calc_total_cost():co = 0for v, k in enumerate(favorite_shops):si, sj = shop_list[k]for b, i, j, u in strategy_away[v]:co += price[b]co += (abs(i - si) + abs(j - sj)) * 5return co# best_strategy_away = None# best_cost = 10 ** 18strategy_away = [[] for _ in range(len(favorite_shops))]while 1:cand = find_best_cand_away()if cand is None:breakcost = calc_total_cost()if DEBUG:print("total cost =", cost)if cost < best_cost:best_cost = costbest_strategy_away = strategy_away[:]if 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)if DEBUG:print("REMOVE Successful", (b, i, j, u))continuebreakb, i, j, v, u = candupdate_candidates_away(b, i, j, v)strategy_away[v].append((b, i, j, u))# strategy_away = best_strategy_awayif DEBUG:print("strategy_away")for v, s in enumerate(strategy_away):print(v, s)def cheapest(strategy):D0 = dijkstra(current_i, current_j)best = 10 ** 18for 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 + sjcost = D0[sij] + D[sij] * 4if cost < best:best = costbest_strategy = (b, i, j, u)best_k = kb, i, j, u = best_strategyk = best_kreturn (b, i, j, u, k, best)# ソート用def f(x, si, sj):b, i, j, u = xreturn (si - i) ** 2 + (sj - j) ** 2# 戦略に基づいてシミュレーション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:breakafter = None# 現在位置から近い方から順に使うwhile strategy_away[v]:(b, i, j, u, k, co) = cheapest(strategy_away[v])si, sj = shop_list[k]if len(strategy_away[v]) == 1 and strategy_stay[v]:# 最後の 1 個は Stay 爆破後の方が良さそうならあとに回すD1 = dijkstra(si, sj)if v + 1 < len(favorite_shops):nsi, nsj = shop_list[favorite_shops[v+1]]D2 = dijkstra(nsi, nsj)route1 = co + D2[si * N + sj]route2 = D1[current_i * N + current_j] + D2[i * N + j]else:route1 = coroute2 = D1[current_i * N + current_j]if route2 < route1:after = (b, i, j, u)strategy_away[v].remove((b, i, j, u))breakmove(si, sj)buy(b)move(i, j)bomb(b)strategy_away[v].remove((b, i, j, u))if 0:# OLD# 基地から近い方から順に使う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)# Stayif strategy_stay[v]:for b, i, j, u in strategy_stay[v]:move(i, j)buy(b)if after is not None:_b, _i, _j, _u = afterbuy(_b)for b, i, j, u in strategy_stay[v]:bomb(b)if after is not None:_b, _i, _j, _u = aftermove(_i, _j)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 += scoreaverage_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")