AtCoder349B_Langton's Takahashi_負の数の余りを効果的に使う

初めに

AtCoder349B_Langton's Takahashiで、余りをを効果的に使う問題で興味深かったため記事にしました。

トーラス状のグリッドとは

初見で問題を解いたときに、意味不明だったのが以下の問題文

このグリッドはトーラス状であるとみなします。すなわち、各 1≤i≤H に対して (i,W) の右に (i,1) があり、各 1≤j≤W に対して (H,j) の下に (1,j) があるとします。

解説動画を見る限り、「グリッドの右端と左端、上端と下端がつながっている」ということを指しているらしい。
（詳しい説明や定義はググってみたが、私には理解できなかったので割愛）

解法ポイント : 負の数の余りを活用する

問題文を見たときの私の気持ち

「グリッドの右端と左端、上端と下端がつながっている」ってどういうこと？？
どうソースコードに落とし込むの？？ -> あたまフリーズ

前提知識：負の数の余りを求める（Python）

pythonは負の数の余りを求めることができます。

print(-1%3)
#>> 2
print(-2%3)
#>> 1
print(-3%3)
#>> 0

負の数の余りを活用する

# 高橋君の向いている方向を変数dで表す
# d=0:上、d=1:右、d=2:下、d=3:左

# 初期化
d = 0

dに1を足すと、高橋君の向いている方向を時計回りに90度動かすことを表現できる。
d = 0 : 上
d = 1 ： +90度して右
d = 2 : +90度して下
d = 3 : +90度して左

ただ、ここでd=3のときに、+1すると4になり範囲を超えてしまう。
操作の回数が少なければ、d=4,5,6,・・・Nまで定義するのも有りだが、
操作が多くなればなるほど、dの数を定義する必要がある。
そこで負の数の余りを利用する。

d = (d + 1) % 4
# こうすることで、d=3以上になっても表現できる。