AtCoderをPythonで取り組んだ振り返り(ABC419 A~D)

どうもこんにちは！

今週のコンテストはA~Dまで完答。
参加者から見て簡単だったんですかね、いつもより早いペースでCやDまで解いている人が多い印象でした。
今回はDまで振り返りです。

問題

問題は以下のリンクから。

A - AtCoder Language -

与えられた文字列がred,blue,greenなら指定された文字列を返し、それ以外の文字列が与えられたらUnknownを返すという問題。
入力を受け取ってif文で場合分けしました。

n = input()

if n == 'red':
    print("SSS")
elif n == 'blue':
    print("FFF")
elif n == 'green':
    print("MMM")
else:
    print("Unknown")

B - Get Min -

下記のクエリが複数与えられるので処理する問題。与えられるクエリは最大100個です。

• 与えられた整数を保持する
• 保持した整数の中で最小の数字を1つ出力し、保持した整数から削除する

シンプルに、クエリで整数が与えられたらリストに保持し、出力するクエリがきたらその中から最小の値を出力して削除するとしました。

n = int(input())
s = []
for i in range(n):
    q = [x for x in input().split()]
    if q[0] == '1':
        s.append(int(q[1]))
    else:
        print(min(s))
        s.remove(min(s))

C - King's Summit -

グリッド上にn個の点が与えられます。この点は時刻ごとにその場にとどまるか上下左右斜めに1マス移動できるとします。この条件のもとで、すべての点が1点に集まれる時刻の最小値を出力する問題。点の最大数は$2×10^5$です。
ポイントは以下と考えました。

• 点は斜めにも動けるので、x方向とy方向を同時に増減が可能
• 時刻の最小値より早く目的地に着いた点はその場にとどまりつづけることができる

これを踏まえると、合流に一番時間がかかるのは距離が一番遠い点同士なので、この２点だけを考えればよいとなります。さらにx,y方向同時に増減できるので、ここでいう距離はマンハッタン距離ではなく、x方向だけもしくはy方向だけで一番遠い点を考えればよいです。
ということで、点の座標をリストに入れればx方向(y方向)の座標でソートして先頭と末端の点で考えればよいとして、以下の通り実装しました。
・・・ま、ここまで整理するのに約1時間+2回WAしましたが。。

import sys

n = int(input())
s = []
for _ in range(n):
    x,y = map(int,input().split())
    s.append((x,y))

# すべての点が同一なら0を出力
if s.count(s[0]) == n:
    print(0)
    sys.exit()

# x方向で中点までで一番遠い点同士の距離を確認
s.sort(key=lambda x:x[0])
ans = abs(s[0][0] - s[n-1][0])

# y方向で中点までの一番遠い点同士の距離を確認
# x軸方向の距離より長い場合は更新
s.sort(key=lambda x:x[1])
ans = max(ans, abs(s[0][1] - s[n-1][1]))

# 中点が割り切れない場合は切り上げ
print((ans+1) // 2 if ans % 2 == 1 else ans // 2)

D - Substr Swap -

同じ長さの2つの文字列S,Tと整数(l,r)の組がm組与えられます。2つの文字列のl文字目からr文字目を入れ替えることをm組分実行した後の文字列Sを出力するという問題。文字列の最大値は$5×10^5$、入れ替えの最大回数は$2×10^5$です。
スライスなどを使って1回1回入れ替えるとTLEになります。l文字目からr文字目という指定と、偶数回入れ替えると変更はないことを利用して、文字ごとの変更回数を累積和を使って算出し、奇数回の文字だけ入れ替えて出力するとして以下のとおり実装しました。

n,m = map(int,input().split())
s = list(input())
t = list(input())

tmp = [0] * (n+1)
for _ in range(m):
    l,r = map(int,input().split())
    tmp[l-1] += 1
    tmp[r] -= 1

# 文字ごとの変更回数の計算
c = [tmp[0]]
for i in range(1,n+1):
    c.append(c[i-1]+tmp[i])

# 奇数回変更する部分は文字を入れ替え
for i in range(n):
    if c[i] % 2 == 1:
        s[i] = t[i]

print("".join(s))        

ではでは。