結果
| 問題 | No.5019 Hakai Project |
| ユーザー |
 Kiri8128
|
| 提出日時 | 2023-11-19 04:51:15 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,100 ms / 3,000 ms |
| コード長 | 11,965 bytes |
| コンパイル時間 | 361 ms |
| コンパイル使用メモリ | 81,828 KB |
| 実行使用メモリ | 198,508 KB |
| スコア | 2,730,278,862 |
| 最終ジャッジ日時 | 2023-11-19 04:52:16 |
| 合計ジャッジ時間 | 56,202 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 985 ms
174,868 KB |
| testcase_01 | AC | 929 ms
168,296 KB |
| testcase_02 | AC | 1,028 ms
191,568 KB |
| testcase_03 | AC | 842 ms
152,972 KB |
| testcase_04 | AC | 994 ms
159,380 KB |
| testcase_05 | AC | 1,039 ms
182,008 KB |
| testcase_06 | AC | 902 ms
161,044 KB |
| testcase_07 | AC | 993 ms
176,280 KB |
| testcase_08 | AC | 980 ms
173,900 KB |
| testcase_09 | AC | 1,097 ms
175,096 KB |
| testcase_10 | AC | 978 ms
169,336 KB |
| testcase_11 | AC | 1,100 ms
177,536 KB |
| testcase_12 | AC | 1,032 ms
166,344 KB |
| testcase_13 | AC | 1,018 ms
170,244 KB |
| testcase_14 | AC | 899 ms
163,608 KB |
| testcase_15 | AC | 970 ms
170,264 KB |
| testcase_16 | AC | 890 ms
155,316 KB |
| testcase_17 | AC | 995 ms
175,100 KB |
| testcase_18 | AC | 887 ms
168,752 KB |
| testcase_19 | AC | 1,019 ms
187,580 KB |
| testcase_20 | AC | 984 ms
171,932 KB |
| testcase_21 | AC | 978 ms
157,852 KB |
| testcase_22 | AC | 1,053 ms
198,508 KB |
| testcase_23 | AC | 996 ms
168,876 KB |
| testcase_24 | AC | 1,085 ms
187,436 KB |
| testcase_25 | AC | 998 ms
178,516 KB |
| testcase_26 | AC | 920 ms
165,700 KB |
| testcase_27 | AC | 1,068 ms
177,952 KB |
| testcase_28 | AC | 1,012 ms
175,592 KB |
| testcase_29 | AC | 1,055 ms
178,528 KB |
| testcase_30 | AC | 811 ms
140,292 KB |
| testcase_31 | AC | 908 ms
161,748 KB |
| testcase_32 | AC | 848 ms
154,472 KB |
| testcase_33 | AC | 930 ms
172,888 KB |
| testcase_34 | AC | 947 ms
154,228 KB |
| testcase_35 | AC | 829 ms
141,944 KB |
| testcase_36 | AC | 853 ms
145,240 KB |
| testcase_37 | AC | 925 ms
169,268 KB |
| testcase_38 | AC | 759 ms
133,200 KB |
| testcase_39 | AC | 1,046 ms
185,696 KB |
| testcase_40 | AC | 930 ms
165,500 KB |
| testcase_41 | AC | 965 ms
171,464 KB |
| testcase_42 | AC | 938 ms
171,336 KB |
| testcase_43 | AC | 959 ms
161,436 KB |
| testcase_44 | AC | 924 ms
166,924 KB |
| testcase_45 | AC | 944 ms
173,200 KB |
| testcase_46 | AC | 1,082 ms
196,852 KB |
| testcase_47 | AC | 911 ms
145,808 KB |
| testcase_48 | AC | 992 ms
175,124 KB |
| testcase_49 | AC | 840 ms
153,028 KB |
ソースコード
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] 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():
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("score =", 1 if building_cnt else comma(10 ** 12 // (10 ** 4 + cost)))
print("A =")
for a in A:
print("".join(a))
print("-" * 20)
print("cost =", cost)
print("score =", 1 if building_cnt else comma(10 ** 12 // (10 ** 4 + cost)))
print("")
try:
LOCAL
except NameError:
LOCAL = 0
if LOCAL:
DEBUG = 1
# N, M, A, Z = random_testcase()
print("Seed ?")
I = input()
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))
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)):
# for ti, tj in ((9, 9), (9, 24), (9, 40), (24, 40), (40, 40), (40, 24), (40, 9), (24, 9)):
# for ti, tj in ((9, 9), (7, 24), (9, 40), (24, 42), (40, 40), (42, 24), (40, 9)):
# for ti, tj in ((9, 9), (9, 20), (9, 30), (9, 40), (20, 40), (30, 40), (40, 40), (40, 30), (40, 20), (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
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
# 基地とする店（お気に入りショップ）を選ぶ
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 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
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
candidates_stay = calc_candidates_stay()
strategy_stay = [[] for _ in range(len(favorite_shops))]
# for _ in range(20):
while 1:
b, i, j, v, ev = find_best_cand_stay()
if ev < 300 * 10 ** 6:
break
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 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]
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]:
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)) * 5
efficiency = 10 ** 6 // (price[b] + moving_cost) * benefit
candidates_efficiency.append(efficiency)
return candidates_away, candidates_efficiency, candidates_matrix
candidates_away, candidates_efficiency, candidates_matrix = calc_candidates_away()
if DEBUG:
print("CHECKPOINT")
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
if DEBUG and best_cand is not None:
print("Best Cand Away =", (b, i, j, v), "Efficiency =", "{:.3f}".format(best / 10 ** 6))
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 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)) * 5
candidates_efficiency[u] -= 10 ** 6 // (price[_b] + moving_cost) * weight[ni][nj]
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)
answer()
disp()