APCS Sep 2021 - g276 Q2 [Python]

問題文:

n × m の盤面に k 体の魔王がいます。魔王 i の初期位置は (r_i, c_i) で、毎ターン (s_i, t_i) だけ移動します。つまり (x, y) から (x + s_i, y + t_i) に移ります。各魔王はそれぞれ r_i、c_i、s_i、t_i の値を持ちます。各ターン、全員が現在位置に爆弾を置いてから移動します。爆弾のあるマスに着地すると爆発し、魔王と爆弾が消えます。2体が同時に同じ爆弾を踏んだ場合は両方とも消え、同じ場所に複数の爆弾があればまとめて爆発します。盤面の外に出た魔王も消えます。魔王が全ていなくなったとき、爆弾が残っているマスはいくつですか？

n, m, k = map(int, input().split())

the_list = [[0 for _ in range(m)] for _ in range(n)]

boss = []

for _ in range(k):
    r, c, s, t = map(int, input().split())
    boss.append([r, c, s, t])

while boss:
    boom = set()
    to_remove = []

    for i in range(len(boss)):
        r, c = boss[i][0], boss[i][1]
        if the_list[r][c] == 0:  # 只有位置為0才要增加
            the_list[r][c] = 1

    for i in range(len(boss) - 1, -1, -1):  # range(起始值, 結束值(不會碰到), 增量) 
        r, c, s, t = boss[i]
        new_r, new_c = r + s, c + t
        
        if new_r >= n or new_c >= m or new_r < 0 or new_c < 0:  # 確認是否超出邊界
            to_remove.append(i)
            continue

        if the_list[new_r][new_c] > 0:
            if (new_r, new_c) not in boom:
                boom.add((new_r, new_c))
            to_remove.append(i)
        else:
            boss[i][0], boss[i][1] = new_r, new_c

    for i in sorted(to_remove, reverse=True): # 確保不會影響要移除的boss順序
        boss.pop(i)
    
    for (r, c) in boom:
        the_list[r][c] = 0

# 計算剩餘的炸彈數量
total = 0
for row in the_list:
    total += sum(row)

print(total)

---

解法レポート：

1. 入力： n、m、k と、各魔王の初期位置・移動ベクトルを読み込みます。
2. 盤面の初期化： 爆弾なしを表す0で埋めた n x m の配列 the_list を作ります。
3. 各ターンのシミュレーション： 全魔王が現在位置に爆弾を置いた後、同時に移動します。盤外に出た魔王は削除します。爆弾のあるマスに着地したら、そのマスを0にして魔王を削除します。
4. 残った爆弾を集計： 魔王が全て消えたら、the_list を走査して残った爆弾を数えます。

ポイント

1. インデックスで削除するときは逆順に走査する：

   • 先頭から要素を削除すると、リストの長さが変わり、後続要素のインデックスがずれます。例えば：

     lst = [1, 2, 3, 4, 5]
     for i in range(len(lst)):
         if lst[i] % 2 == 0:
             lst.pop(i)
     

   lst[1] を削除すると [1, 3, 4, 5] になりますが、インデックスは増え続けるため、次の偶数 4 を飛ばしてしまいます。

   • 逆順なら、まだ処理していない要素のインデックスに影響しません。

     lst = [1, 2, 3, 4, 5]
     for i in range(len(lst) - 1, -1, -1):
         if lst[i] % 2 == 0:
             lst.pop(i)
     

   削除位置より後ろの要素は既に処理済みなので、影響を受けません。

この問題で使う知識：

• シミュレーション
• リスト操作
• 集合

---

• [✔️] 必要であればコードをそのまま使用できます。
• [✔️] 共有する際は出典を明記してください。
• [✔️] うーん……今回は少し遅かったです。

この記事は繁体字中国語の原文をAIで翻訳したものです。意味や表現に違いがある可能性があります。正確な内容は繁体字中国語の原文をご確認ください。