問題はこちら
最初の回答
import copy
nq = list(map(int, input().split()))
n = nq[0]
q = nq[1]
Q = []
for i in range(q):
Q.append(list(input().split()))
N = []
for i in range(n):
N.append([i+1, 0])
#nは龍の位置リスト
def exe_1(n, C):
tmp = copy.deepcopy(n)
n = n[-1:] + n[:-1]
match C:
case "R":
n[0][0] = tmp[0][0] + 1
n[0][1] = tmp[0][1]
case "L":
n[0][0] = tmp[0][0] - 1
n[0][1] = tmp[0][1]
case "U":
n[0][0] = tmp[0][0]
n[0][1] = tmp[0][1] + 1
case "D":
n[0][0] = tmp[0][0]
n[0][1] = tmp[0][1] - 1
return n
def exe_2(n, p):
return " ".join(list(map(str, n[p-1])))
for i in range(q):
query = Q[i]
match query[0]:
case "1":
C = query[1]
N = exe_1(N, C)
case "2":
print(exe_2(N, int(query[1])))
正しい回答は出せていた(はず)なのですが、TLEとなりました。
作り直した回答
作り直して正解をいただけたのがこちら。
n, q = map(int, input().split())
Q = [list(input().split()) for i in range(q)]
N = [(i+1, 0) for i in range(n)][::-1]
for i in range(q):
if Q[i][0] == "1":
x, y = N[-1]
if Q[i][1] == "R":
x += 1
N.append((x, y))
elif Q[i][1] == "L":
x -= 1
N.append((x, y))
elif Q[i][1] == "U":
y += 1
N.append((x, y))
elif Q[i][1] == "D":
y -= 1
N.append((x, y))
else:
print(*N[-int(Q[i][1])])
かなりスッキリしました。
実行時間も、2000msを超えていたところから579msとかなり短縮されました。
改善した点
変数の取得
nq = list(map(int, input().split()))
n = nq[0]
q = nq[1]
この部分です。
正直よくわかっていなかったので、リストを作ってそのi番目の要素を変数へ……としていたのですが。
n, q = map(int, input().split())
これで良いことに、振り返り中に気づきました。
何をやっていたのでしょうか……。
リストの生成
Q = []
for i in range(q):
Q.append(list(input().split()))
N = []
for i in range(n):
N.append([i+1, 0])
ここも、もっと簡単に書けました。
Q = [list(input().split()) for i in range(q)]
N = [[i+1, 0] for i in range(n)][::-1]
これで良いですね。
処理の内容は同じなのですが、可読性がかなり違います。
アルゴリズムの修正
最初は、龍の現在位置をリストに格納しようとしていたため、操作のたびにリストの要素の直接操作が(龍の長さ)回発生していました。
リストの要素の直接操作はかなりメモリを使うらしく、どうもここが実行時間を伸ばしていた原因のようです。
そこで、リストをリバースしてから操作後の位置をリストの末尾に追加していくことにしました。
リストはどんどん長くなっていくのが気持ち悪いですが、末尾の要素を毎回削除するよりも処理が軽くなります。
この辺りはアルゴリズム的な思考を身につけないといけないなと痛感しました……。
データ型
龍の位置情報のデータ型を、リストよりも処理が軽いというタプルに変更。
リスト型で書いたときの実行時間は1048msだったので、改善幅は約500msと、無視できない差が生まれています。