概要

ロボットが円形の座席上を移動し、各命令後に指している座席の空腹度を記録していく。最終的に記録された空腹度の総和を求める問題。

考察

この問題では、ロボットが円形に並んだ \(N\) 個の座席の上を移動します。それぞれの座席には空腹度 \(A_i\) が設定されており、ロボットがその座席を指すたびにその値を合計していきます。

重要なポイントは、ロボットの移動が「円形」であることです。つまり、座席 \(N\) の次は座席 \(1\) に戻り、座席 \(1\) の前は座席 \(N\) になります。これは剰余演算（mod）を使うことで簡単に実現できます。

素朴な方法として、毎回現在位置を更新して対応する \(A_i\) を加算していくシミュレーションを行えばよいです。制約が \(Q \leq 10^5\) なので、各命令に対して定数時間で処理できれば間に合います。

この問題で誤った実装になりやすいのは、位置の更新時に境界処理を間違えることです。特に、負の値に対する mod の扱いには注意が必要です（Python では負の数の % N は正の結果を返してくれるので安全ですが、他の言語では場合分けが必要です）。

アルゴリズム

1. 座席数 \(N\)、命令数 \(Q\)、空腹度リスト \(A\)、命令文字列 \(S\) を読み込む。
2. ロボットの初期位置 pos を \(0\)（0-indexed）とする。
3. 合計値 total を \(0\) で初期化する。
4. 文字列 \(S\) を先頭から順に処理する：
   • R の場合は pos = (pos + 1) % N とする。
   • L の場合は pos = (pos - 1 + N) % N とする（負にならないように調整）。
   • 更新後の pos に対応する \(A[pos]\) を total に加算する。
5. 最終的な total を出力する。

計算量

• 時間計算量: \(O(Q)\)
  各命令につき定数時間で処理できるため、全体で \(Q\) 回の操作で \(O(Q)\)。
• 空間計算量: \(O(N)\)
  空腹度の配列 \(A\) を保持するのに \(O(N)\) 必要。

実装のポイント

• 座席のインデックスを 0-indexed として扱うと、mod の計算が楽になります。

• L のときの位置更新で (pos - 1 + N) % N としているのは、負の数を避けるためです。

• Python では負の数の % N も正の結果になるので、必ずしも + N は必要ありませんが、他の言語への移植を考えると明示的に書く方が無難です。

  ソースコード

N, Q = map(int, input().split())
A = list(map(int, input().split()))
S = input().strip()

pos = 0  # 0-indexed
total = 0

for command in S:
    if command == 'R':
        pos = (pos + 1) % N
    else:  # command == 'L'
        pos = (pos - 1 + N) % N
    total += A[pos]

print(total)

この解説は qwen3-coder-480b によって生成されました。