キーワード
問題
問題文
注：この問題はF問題とほぼ同じ設定です。
本文中で太字で示されている部分および制約のみが異なります。
あなたはあるリングを両手で握っています。
このリングはN (N≥3)個のパーツ1,2,…,Nによって構成されており、パーツiとパーツi+1(1≤i≤N−1)、およびパーツ1とパーツNがそれぞれ隣接しています。
最初、左手はパーツ1を、右手はパーツ2を握っています。
あなたは、1回の操作で以下のことを行えます。
片方の手を、今握っているパーツに隣接するいずれかのパーツに移動する。
ただし、移動先にもう一方の手がない場合に限る。
以下の図は、初期状態およびそこから行える操作と行えない操作の例を示したもので、リングの各パーツに書き込まれた数はそのパーツの番号を、Lと書かれた丸は左手を、Rと書かれた丸は右手を示しています。
あなたは今から与えられるQ個の指示に順番に従う必要があります。
i (1≤i≤Q)個目の指示は文字Hiおよび整数Tiによって表され、その意味は以下の通りです：操作を何回か（0回でもよい）行うことで、HiがLならば左手、Rならば右手が、パーツTiを握っている状態にする。
このとき、Hiによって指定された手ではない方の手を動かしてはならない。
なお、達成可能な指示しか与えられないことが保証されます。
詳細この問題の設定の下では、各iについて、i個目の指示に従う直前でのそれぞれの手の位置が一意に定まることが証明できます。
このとき、左手の位置をパーツli、右手の位置をパーツriとおくと、Hi=LならばTi≠riが、Hi=RならばTi≠liがそれぞれ保証されます。
すべての指示に従うために必要な操作回数の合計の最小値を求めてください。
制約
3≤N≤100
1≤Q≤100
Hi は L または R
1≤Ti≤N
N,Q,Ti は整数
達成可能な指示しか与えられない（詳細は問題文を参照してください）
入力
入力は以下の形式で標準入力から与えられる。
N Q
H1 T1
H2 T2
⋮
HQ TQ
出力
すべての指示に従うために必要な操作回数の合計の最小値を出力せよ。
入力例 1
6 3
R 4
L 5
R 6
出力例 1
8
以下のように操作を行うことで、Q 個の指示すべてに順番に従うことができます。
右手をパーツ 2→3→4 と移動させることで、1 番目の指示に従う。
左手をパーツ 1→6→5 と移動させることで、2 番目の指示に従う。
右手をパーツ 4→3→2→1→6 と移動させることで、3 番目の指示に従う。
このとき行う操作回数の合計は 2+2+4=8 であり、これが最小です。
（3 番目の指示に従う際に右手をパーツ 4→5→6 と移動させることはできないことに注意してください。）
入力例 2
100 2
L 1
R 2
出力例 2
0
操作を 1 度も行わずに指示に従うことができる場合もあります。
入力例 3
30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16
出力例 3
92
回答
n, q = map(int, input().split())
list = []
for i in range(q):
h, t = input().split()
list.append([h, int(t)])
print(list)
L = 1
R = 2
key = 0
a=0
b=0
for i in list:
a_flag = True
b_flag = True
if i[0] == "R":
a=b= i[1] % n
while a != i[1] or b != i[1]:
if a_flag == True:
a = (a + 1) % n
if a == L:
a_flag = False
if b_flag == True:
b = (b + 1) % n
if b == L:
b_flag = False
key += 1
if i[0] == "L":
a=b= i[1]
while a != i[1] or b != i[1]:
if a_flag == True:
a = (a + 1) % n
if a == R:
a_flag = False
if b_flag == True:
b = (b + 1) % n
if b == R:
b_flag = False
key += 1
print(key)
参考
備考
- 供養です。一生懸命書いたのに実行時間超過で実行できませんでした。そもそも意図した挙動になっているかどうかも分かりません。
- なんとなく今のままの学習で良いのかよくわからなくなっていた。確かにコードを書けるようになったが、綺麗なコードは書けないし、ほんとにそれっぽいコードを書けるようになったという感じ。
- 具体的に一つの問題に対して、あれがこうでとかを考えるより、もう少し抽象論を理解した方がいい気がする。今の所頭の中でプログラムが全然整理できていない。もう少し頭の中を整理して、問題に対して様々な解決策を検討して、その中のベストプラクティスを考えるようにしたい。
- 現状は一つ解決策を見つけたらそこにしがみつくしかない。とはいえ、具体の蓄積が抽象だし、解決策の選択肢を増やすには、解決策を知るしかない。
- もう少し、人のコードをよく読んで、感動する時間を多く作りたい。