結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 Kiri8128
|
| 提出日時 | 2023-11-19 15:47:34 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,355 ms / 3,000 ms |
| コード長 | 21,546 bytes |
| コンパイル時間 | 475 ms |
| コンパイル使用メモリ | 81,700 KB |
| 実行使用メモリ | 271,676 KB |
| スコア | 2,858,939,011 |
| 最終ジャッジ日時 | 2023-11-19 15:50:02 |
| 合計ジャッジ時間 | 110,599 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,063 ms
268,648 KB |
| testcase_01 | AC | 2,100 ms
262,660 KB |
| testcase_02 | AC | 2,264 ms
271,676 KB |
| testcase_03 | AC | 1,911 ms
242,348 KB |
| testcase_04 | AC | 1,930 ms
257,172 KB |
| testcase_05 | AC | 2,178 ms
271,364 KB |
| testcase_06 | AC | 2,049 ms
263,340 KB |
| testcase_07 | AC | 2,107 ms
267,732 KB |
| testcase_08 | AC | 2,048 ms
261,464 KB |
| testcase_09 | AC | 2,355 ms
271,184 KB |
| testcase_10 | AC | 1,837 ms
247,476 KB |
| testcase_11 | AC | 2,163 ms
268,372 KB |
| testcase_12 | AC | 2,044 ms
257,220 KB |
| testcase_13 | AC | 2,190 ms
270,692 KB |
| testcase_14 | AC | 1,965 ms
260,804 KB |
| testcase_15 | AC | 2,020 ms
261,032 KB |
| testcase_16 | AC | 1,937 ms
235,800 KB |
| testcase_17 | AC | 1,900 ms
256,924 KB |
| testcase_18 | AC | 2,050 ms
271,644 KB |
| testcase_19 | AC | 2,249 ms
269,584 KB |
| testcase_20 | AC | 1,908 ms
222,780 KB |
| testcase_21 | AC | 2,053 ms
244,220 KB |
| testcase_22 | AC | 2,006 ms
265,804 KB |
| testcase_23 | AC | 2,220 ms
269,888 KB |
| testcase_24 | AC | 2,308 ms
269,192 KB |
| testcase_25 | AC | 2,134 ms
266,352 KB |
| testcase_26 | AC | 2,128 ms
266,652 KB |
| testcase_27 | AC | 2,088 ms
268,616 KB |
| testcase_28 | AC | 2,015 ms
259,480 KB |
| testcase_29 | AC | 2,100 ms
271,488 KB |
| testcase_30 | AC | 2,008 ms
235,252 KB |
| testcase_31 | AC | 2,211 ms
253,168 KB |
| testcase_32 | AC | 2,071 ms
260,796 KB |
| testcase_33 | AC | 2,017 ms
262,252 KB |
| testcase_34 | AC | 2,055 ms
235,000 KB |
| testcase_35 | AC | 2,003 ms
247,160 KB |
| testcase_36 | AC | 1,855 ms
224,716 KB |
| testcase_37 | AC | 2,165 ms
270,640 KB |
| testcase_38 | AC | 1,748 ms
196,344 KB |
| testcase_39 | AC | 2,170 ms
269,832 KB |
| testcase_40 | AC | 2,120 ms
246,376 KB |
| testcase_41 | AC | 2,144 ms
271,256 KB |
| testcase_42 | AC | 1,989 ms
260,932 KB |
| testcase_43 | AC | 2,018 ms
263,356 KB |
| testcase_44 | AC | 1,973 ms
228,528 KB |
| testcase_45 | AC | 1,916 ms
242,184 KB |
| testcase_46 | AC | 1,989 ms
253,788 KB |
| testcase_47 | AC | 1,935 ms
221,268 KB |
| testcase_48 | AC | 2,217 ms
254,076 KB |
| testcase_49 | AC | 1,958 ms
226,368 KB |
ソースコード
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 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, best)
# ソート用
def f(x, si, sj):
b, i, j, u = x
return (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:
break
after = 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]:
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 = co
route2 = D1[current_i * N + current_j]
if route2 < route1:
after = (b, i, j, u)
strategy_away[v].remove((b, i, j, u))
break
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)
# Stay
if 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 = after
buy(_b)
for b, i, j, u in strategy_stay[v]:
bomb(b)
if after is not None:
_b, _i, _j, _u = after
move(_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 += 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")