【競プロ第2回】 AtCoder ABC199-CをPythonで解く - スマレジエンジニアyushiのブログ

初めてAtCoderのコンテストに参加してみました。

しかしC問題でTLE（Time Limit Exceeded）に悩まされたので、その解説です。

問題

C - IPFL

"IPFL"というタイトルですが、これは"FLIP"のアナグラムです。

詳しくは問題文の通り...。

TLEした版

問題文を読む限りは、処理は単純でそんなに難しくなさそうに見えます。

というわけで地道にロジックを書いてみます。

def main():
  N = int(input())
  S = input()
  Q = int(input())
  TAB = [input() for _ in range(Q)]
 
  for tab in TAB:
    if tab[0] == '2':
      S = S[N:] + S[:N]
    else:
      tab = tab.split()
      a_index = int(tab[1]) - 1
      b_index = int(tab[2]) - 1
      S = S[:a_index] + S[b_index] + S[a_index + 1:b_index] + S[a_index] + S[b_index + 1:]
 
  print(S)
 
main()

問題文の通りに、しかしまずまずスッキリかけたなと思いつつ提出してみます。

すると、実行時間"2207 ms"でTLE、すなわち時間制限超過してしまいました。

修正版

※ 結局時間内に解けず、他の人の回答を見ながら理解しました。

def main():
  from builtins import int
 
  from sys import stdin
  input = stdin.readline
 
  N = int(input())
  S = list(input()[:-1])
  S1 = S[:N]
  S2 = S[N:]
  Q = int(input())
 
  for _ in [0] * Q:
    tab = input()
    if tab[0] == '2':
      S1, S2 = S2, S1
    else:
      tab = tab.split()
      a_index = int(tab[1]) - 1
      b_index = int(tab[2]) - 1
 
      if b_index < N:
        S1[a_index], S1[b_index] = S1[b_index], S1[a_index]
      elif a_index >= N:
        a_index -= N
        b_index -= N
        S2[a_index], S2[b_index] = S2[b_index], S2[a_index]
      else:
        b_index -= N
        S1[a_index], S2[b_index] = S2[b_index], S1[a_index]
 
  print(''.join(S1 + S2))
 
main()