概要

ロボットの移動を命令通りにシミュレーションし、訪れたマスに荷物（#）があればその場で回収して消していき、最後に残った荷物数を求めます。

考察

この問題で必要なのは「最終的に回収されなかった # の個数」です。
命令は最大 \(N=2\times 10^5\) 個ですが、各命令につきロボットは高々 1 マス移動するだけなので、1 命令を \(O(1)\) で処理できれば全体でも十分間に合います。

重要な観察は以下です。

• ロボットがいるマスが # なら、その荷物は回収されて以後は存在しない。
• 同じマスを何度訪れても、最初に回収した後は何も起こらない。
  → つまり「回収済み」を記録すればよい。

素朴に「命令を実行するたびに盤面全体を走査して残りの # を数える」などをすると、最悪で \(O(NHW)\) となり確実に TLE します。
そこで、

• 最初に # の総数 total を数えておく
• ロボットが # のマスに来たら、そのマスを .（回収済み）にして total を 1 減らす

とすれば、盤面全体の再走査は不要になります。

アルゴリズム

1. 入力されたグリッド \(S\) を保持しつつ、最初の # の個数を数えて total に入れる。
2. ロボット位置を左上 \((1,1)\)（0-index なら \((0,0)\)）に置く。
3. 初期位置に # があれば回収し、グリッド上で消して total -= 1。
4. 命令列 \(T\) を先頭から順に処理する。
   • U/D/L/R に応じて移動先がグリッド内なら座標を更新、外なら無視（座標そのまま）。
   • 移動（または無視）後のマスに # があれば回収し、消して total -= 1。
5. すべての命令後、total を出力する。

この方法では「回収済み」はグリッドを直接書き換える（#→.）ことで表現でき、同じマスを再訪しても二重に減らさないことが保証されます。

計算量

• 時間計算量: \(O(HW + N)\)（初期の # カウントが \(HW\)、命令処理が \(N\)）
• 空間計算量: \(O(HW)\)（グリッド保持）

実装のポイント

• 座標は 0-index（r,c を \(0 \le r < H,\, 0 \le c < W\)）で管理すると境界判定が簡単です。

• 「残り個数」を毎回数え直すのではなく、最初に数えた総数から回収のたびに 1 減らすのが高速です。

• 提示コードでは高速化のため、グリッドを bytearray の真偽値配列として持ち、命令列も bytes として処理しています（ord('U')=85 など）。これにより Python でも \(N=2\times 10^5\) を安定して処理できます。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    H, W, N = map(int, input().split())

    grid = []
    total = 0
    for _ in range(H):
        s = input().strip()
        total += s.count(b'#')
        row = bytearray(b == 35 for b in s)  # 35 == ord('#')
        grid.append(row)

    T = input().strip()

    r = c = 0
    if grid[0][0]:
        grid[0][0] = 0
        total -= 1

    for b in T:
        if b == 85:  # 'U'
            if r > 0:
                r -= 1
        elif b == 68:  # 'D'
            if r + 1 < H:
                r += 1
        elif b == 76:  # 'L'
            if c > 0:
                c -= 1
        else:  # 'R'
            if c + 1 < W:
                c += 1

        if grid[r][c]:
            grid[r][c] = 0
            total -= 1

    print(total)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。