from heapq import heapify, heappush as hpush, heappop as hpop def dijkstra(i0, j0, target_i, target_j): ij0 = i0 * N + j0 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) 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) 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("") 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 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]: 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 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] try: LOCAL except NameError: LOCAL = 0 loop = 1 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)) for lp in range(loop): 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)) # 基地とする店(お気に入りショップ)を選ぶ 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 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 < 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 and 0: print("candidates_stay =", candidates_stay) if DEBUG: 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 = calc_candidates_away() if DEBUG: print("CHECKPOINT") 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()