AtCoder Beginner Contest 199 A〜C問題

AtCoder Python

前書き

AtCoder Beginner Contest 199に参加しました。

A問題

  • 時間：2分
  • 難易度：灰
A,B,C=map(int,input().split())
if A**2+B**2<C**2: print('Yes')
else: print('No')

B問題

  • 時間：4分
  • 難易度：灰

atcoder.jp

配列A , Bに格納されている要素で全てのiでAi ≤ x ≤Biを満たすxの個数を探します。
A

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
if min(B)-max(A)<0: print(0)
else: print(min(B)-max(A)+1)

C問題

  • 時間：70分
  • 難易度：？

T == 1の時は文字の入れ替え
T == 2の時は文字列前半と後半の入れ替えをします。

条件は以下の通りです。
1 ≤ Q ≤ 3*10**5
1 ≤ N ≤ 2*10**5

TLEした理由

普通に解こうとしたらTLEを連発しました。
なので工夫をしなければなりません。

文字列前半と後半の処理についてですが、配列からスライス処理はスライスする要素数をkすると、O(k)となります。
つまり最大でもO(2*10**5)になります。
ただでさえ1 ≤ Q ≤ 3*10**5なので、そりゃTLEしますよね・・・。

解決策

(1). 文字列前半後半入れ替え処理の回数を0 or 1回に

計算量を喰う文字列前半と後半の入れ替え処理の回数を減らしてやり必要があります。
→ 0 or 1回で済むようにします。
→ 文字列前半後半入れ替え処理の総回数は奇数の時は最後1回、偶数の時は0回になるようにします。
→ ただ途中にT == 1（文字入れ替え）が挟むので一見複雑です。

(2). 文字入れ替え処理に工夫を

処理時点の文字列前半後半入れ替え処理回数をcountと定義します。

count = 偶数の時
→文字入れ替え処理は通常通り
→ A-1番目とB-1番目を入れ替え

count = 奇数の時
→配列の要素を指定する時にNだけずらして入れ替えてやる
→ A-1-N番目とB-1-N番目を入れ替え
→ Nだけずらすことで(1)の矛盾を無くせる

これでもモヤモヤが残る場合は、問題のサンプルデータを使って実際に試してみてください。

N=int(input())
S=list(input())
Q=int(input())
count=0
for i in range(Q):
  T,A,B=map(int,input().split())
  if T==2:
    count+=1
  if count%2==0:
    k=S[A-1]
    S[A-1]=S[B-1]
    S[B-1]=k
  else:
    k=S[A-1-N]
    S[A-1-N]=S[B-1-N]
    S[B-1-N]=k

if count%2==0: print(''.join(S))
else: print(''.join(S[-N:]+S[:N]))