ABC244 Bのように、各命令の結果がその時点の状態だけで決まる問題は、状態を持って入力を左から一度ずつ処理すれば解けます。現在座標をxとy、向きをdの3つに絞り、Sでは更新前の向きへ1歩進み、Rでは座標を変えず向きだけを右へ1つ進めます。Nの上限は105で、各命令を定数時間で処理できるため、直接シミュレーションを選べます。
この問題で最後に必要なのは、全命令を処理したあとのxとyです。途中の全座標を保存する必要はありません。ただし、次のSがどちらへ進むかは現在の向きで変わるので、位置だけでなくdも同時に持ちます。
状態を現在座標と向きに絞る
座標は(x, y)で表します。x軸の正方向を東、y軸の正方向を北とし、初期値は原点(0, 0)、向きは東です。向きdは東・南・西・北を0から3までの整数に対応させます。
d | 向き | 方向ベクトル | Sで行う座標更新 |
|---|---|---|---|
| 0 | 東 | (1, 0) | x += 1 |
| 1 | 南 | (0, -1) | y -= 1 |
| 2 | 西 | (-1, 0) | x -= 1 |
| 3 | 北 | (0, 1) | y += 1 |
Sを読むときは、表から現在のdに対応する変化を座標へ加え、dはそのままにします。Rを読むときは座標を変えず、d = (d + 1) % 4で東→南→西→北→東と1つ進めます。したがって、Rの直後のSは回転後の向きで移動します。1命令で移動と回転の両方を行うわけではありません。
構成例SRSRRSを1命令ずつ追う
次の表は公式サンプルではなく、状態と更新順を確かめるために構成した例です。N=6、命令列はT=SRSRRS、初期状態は(x, y, d)=(0, 0, 東)とします。
| 命令番号 | 命令 | 処理前 | 行う操作 | 処理後 |
|---|---|---|---|---|
| 1 | S | (0, 0, 東) | 東へ1進む | (1, 0, 東) |
| 2 | R | (1, 0, 東) | その場で右へ90度回る | (1, 0, 南) |
| 3 | S | (1, 0, 南) | 南へ1進む | (1, -1, 南) |
| 4 | R | (1, -1, 南) | その場で右へ90度回る | (1, -1, 西) |
| 5 | R | (1, -1, 西) | その場で右へ90度回る | (1, -1, 北) |
| 6 | S | (1, -1, 北) | 北へ1進む | (1, 0, 北) |
Sは3回あり、その3回だけが座標を変えています。Rは3回とも座標を保ったまま向きだけを変えるため、最後の状態は(1, 0, 北)です。問題が出力するのは座標だけなので、この例の出力は1 0になります。これは公式サンプルの結果ではありません。
表の3行目では、2行目のRで向きが南になったあと、その向きを使ってyを1減らしています。6行目では、4行目と5行目の回転を反映した北向きでyを1増やします。プログラムでも、Sの分岐で現在のdを配列から読み、Rの分岐で座標を触らずにdだけを更新します。
ABC244 Bの公式仕様とサンプル
ABC244 B – Go Straight and Turn Rightは、xy平面上で命令列を順に実行し、最後の位置を求める問題です。原点(0, 0)で東を向いた状態から、長さNの文字列Tを先頭から読みます。文字がSなら現在の向きへ距離1だけ進み、Rなら位置を変えず右へ90度回転します。すべての命令を終えたら、xとyを空白区切りで出力します。
ABC244 Bの公式解説も、位置(x, y)と向きdを保持し、Tを先頭から走査してSとRに応じて状態を更新する直接シミュレーションを示しています。公式解説ではd=0を東、d=1を南、d=2を西、d=3を北としています。
| 項目 | 公式の条件 |
|---|---|
N | 1 ≤ N ≤ 105、Nは整数 |
T | SとRだけからなる長さNの文字列 |
| 実行時間制限 | 2秒 |
| メモリ制限 | 1024 MiB |
公式サンプル1
入力と期待出力は、公式問題文のものをそのまま示します。
4
SSRS出力：
2 -1公式サンプル2
20
SRSRSSRSSSRSRRRRRSRR出力：
0 1入力から出力までのPython参考コード
公式入力は、整数Nと文字列Tの2項目です。標準入力を空白で分けて読み、Tの各文字を順に処理します。向きごとの座標変化をdxとdyに並べておくと、Sの処理は現在のdで配列を参照するだけです。公式制約でTはSとRだけなので、S以外の分岐をRとして扱えます。
import sys
data = sys.stdin.buffer.read().split()
N = int(data[0])
T = data[1].decode()
dx = (1, 0, -1, 0)
dy = (0, -1, 0, 1)
x = 0
y = 0
direction = 0
for command in T:
if command == "S":
x += dx[direction]
y += dy[direction]
else:
direction = (direction + 1) % 4
print(x, y)direction=0は東を表し、dxとdyの同じ添字が表の方向ベクトルに対応します。Sでは更新前のdirectionを使って座標を変え、Rでは(direction + 1) % 4だけを実行します。最後にprint(x, y)で座標だけを出力するため、向きは出力へ混ざりません。
不変条件で正しさを確かめる
ループの途中で正しい状態を保てているかを、次の不変条件で確認します。0 ≤ k ≤ Nのとき、先頭からk文字を処理した直後のプログラムの(x, y, direction)が、公式手順で先頭k命令を実行したあとの位置と向きを表す、とします。
k=0では、プログラムはx=0、y=0、direction=0で始まります。これは公式の初期状態である原点・東向きと一致するため、不変条件は最初に成立します。
次の文字がSなら、プログラムは現在のdirectionに対応するdx[direction]とdy[direction]を座標へ加え、向きは変えません。表の4つの方向ベクトルは、現在の向きへ距離1だけ進む公式の動作そのものなので、処理後も公式手順の状態と一致します。
次の文字がRなら、プログラムは座標を変えず、direction = (direction + 1) % 4で東・南・西・北の循環を1つ進めます。これは位置を保ったまま右へ90度回転する公式の動作と一致します。
どちらの命令でも、次の1文字を処理したあとに不変条件が保たれます。したがってN文字すべてを処理したあとも、プログラムの(x, y)は公式手順の最終座標であり、出力は問題の答えになります。
計算量と境界を確認する
ループは長さNのTを1回だけ走査します。各命令では、条件判定、方向配列の参照、整数の加算、または剰余を使った向きの更新だけを行うため、時間計算量はO(N)です。Tを入力文字列として保持するので使用メモリはO(N)で、Tを除く座標・向き・方向配列の追加メモリはO(1)です。
次の表は公式サンプルではなく、公式の規則から構成した境界の確認例です。最終方向は問題の出力対象ではないため、必要な場合だけ補足しています。
| 入力の形 | 最終座標 | 確認すること |
|---|---|---|
N=1, T=S | (1, 0) | 東向きの初期状態で1歩進む |
N=1, T=R | (0, 0) | 回転だけでは座標が変わらない |
Sを長さNだけ並べる | (N, 0) | 向きが変わらない間は東へ進み続ける |
Rだけを並べる | (0, 0) | 何回回っても移動しない |
N=4, T=RRRR | (0, 0)、最後は東向き | 4回の右回転で向きが元へ戻る |
N=2, T=RS | (0, -1) | 回転後の南向きで進み、負の座標も扱う |
特にRSでは、先にRで南を向き、そのあとSでyを1減らします。Sのあとに回転するよう順番を入れ替えると別の結果になるため、命令を読んだ順に1つずつ状態を確定させることが大切です。
次は更新順が増えるABC265 B
状態を1命令ずつ更新する考え方を、時間の消費と到着時のボーナスへ広げる次の練習がABC265 B – Exploreです。部屋1から部屋Nまで順に移動し、最初は持ち時間Tを持っています。部屋iから部屋i+1へ移るときにAiを消費し、移動後の持ち時間が0以下なら、その移動はできません。ボーナス部屋へ到着したときだけ、その部屋に対応するYiを加えます。
ABC265 Bの公式解説は、部屋間の移動を直接シミュレーションし、部屋ごとに到着時の獲得時間を配列へ持つ方針を説明しています。公式の制約は次のとおりです。
| 項目 | 公式の条件 |
|---|---|
N | 2 ≤ N ≤ 105 |
M | 0 ≤ M ≤ N−2 |
T | 1 ≤ T ≤ 109 |
Ai | 1 ≤ Ai ≤ 109 |
| ボーナス部屋 | 1 < X1 < … < XM < N、1 ≤ Yi ≤ 109 |
| その他 | 入力に含まれる値はすべて整数 |
| 実行時間制限 | 2秒 |
| メモリ制限 | 1024 MiB |
更新順を公式サンプルで比べると違いがはっきりします。公式入力例1はN=4、M=1、初期時間T=10、移動時間(5, 7, 5)、部屋2のボーナス10で、部屋2へ着いたあとに10を加えられるため出力はYesです。公式入力例2は移動時間が(10, 7, 5)で、最初の移動後に残り時間が0になります。この移動はできず、部屋2のボーナスを先に加えないため出力はNoです。
ABC244 Bでは命令ごとに座標または向きの一方を更新しました。ABC265 Bでは、まずAiを引き、0以下なら失敗と判定し、到着できたときだけボーナスを加える、という順序を状態へ組み込みます。次に解くときは、現在の状態、1回の操作で変わる値、失敗判定を置く位置、成功後に加える値をこの順に書き出すと、問題文をループへ移しやすくなります。
