Atcorder_ABC199：C問題のTLE解決できず

参加は二回目ですが、残念ながらA, Bの2完。

当分はCまでの完答を目標にしていたので、早くも残念な結果に。

Cはアルゴリズムは構築できたが、規定時間内に処理できないため提出できず。

提出したコードの記録を残すとともに、C問題の解析を実施しました。

A問題

a, b, c = map(int, input().split())
if (a**2)+(b**2) < (c**2):
    print("Yes")
else:
    print("No")

1分30秒で提出。

B問題

A = []
B = []
N = int(input())

A = list(map(int,  input().split()))
B = list(map(int,  input().split()))

if min(B)-max(A)+1 > 0:
    print(min(B)-max(A)+1)
else:
    print(0)

7分30秒で提出。

C問題

自身が提出したコード：TLE

N = int(input())
S = input()
Q = int(input())
s = list(S)
# 以降、Sはリストとして扱う
for i in range(Q):
    t, a, b = map(int, input().split())

    if t == 2:  # 前半後半を入れ替える
        s[0:N], s[N:2 * N] = s[N:2 * N], s[0:N]

    else:   #AiとBiを入れ替える
        s[a - 1], s[b - 1] = s[b - 1], s[a - 1]
S = "".join(s)
print(S)

2213 ms (制限時間2,000msなので、213msオーバー (>_<)

・文字列Sは即座にリストsに変換する (例: FLIP→'F', 'L', 'I', 'P')

・クエリ先頭tに応じて分岐処理する (2 or 1)

解答例：AC

N = int(input())
S = input()
Q = int(input())
s0, s1 = list(S[:N]), list(S[N:2*N])
# 以降、Sはリストとして扱う
for i in range(Q):
    t, a, b = map(int, input().split())

    if t == 2:  # 前半後半を入れ替える
        s0, s1 = s1, s0

    else:   #AiとBiを入れ替える
        if b <= N:
            s0[a-1], s0[b-1] = s0[b-1], s0[a-1]
        elif N < a:
            s1[a - 1 -N], s1[b - 1 - N] = s1[b - 1 - N], s1[a - 1 - N]
        else:
            s0[a - 1], s1[b - 1 - N] = s1[b - 1 - N], s0[a - 1]

S = "".join(s0 + s1)
print(S)

実行時間：459 ms (約1/5の処理時間に短縮)

・文字列Sは即座に2つのリストに分解する

【メリット】

・各リストが最大２×10^5文字まで短縮でき、前半後半の入れ替えがスムーズ

（分割しない場合、最大4×10^5文字になる可能性がある）

今回の反省点

• 日々、計算時間を配慮に入れた演習を心がける
• 処理時間が早い参加者のコードを参照して写経する
• 処理内容に応じてリスト分割できないか試験中に検討する