AtCoder ABC419 振り返り(PythonでABCD問題)

ABC419を振り返ります

今回はABCDまで4問解答でした。D問題まで解けて結構手応えがあったんですが、順位的には5000位くらいでふるわず。レーティングは微減でした。C,D問題を解けた人が多かったようです。

解いている時は、C・Dともに結構難しいと思ったんですけど...。Cはアルゴリズムを使わずに考察で解ける、Dは累積和の使い方を知っていれば解けるということで、難易度が下がったのかもしれません。

A - AtCoder Language

素直にif文で場合分けをしました。コピペミスがないように気を使います...。

S = input()

# Sの文字列に応じて出力を変える
if S == 'red':
    print("SSS")
elif S == 'blue':
    print("FFF")
elif S == 'green':
    print("MMM")
else:
    print("Unknown")

B - Get Min

「順位付きキューを使うのかな」とか考えましたが、最大100個のクエリなので通常のリストで十分間に合います。

Q = int(input())
balls = []

# Q回のクエリを処理
for i in range(Q):
    query = input().split()

    if query[0] == "1":
        # クエリが1の場合、ボールを追加
        x = int(query[1])
        balls.append(x)
    elif query[0] == "2":
        # クエリが2の場合、最小のボールを削除
        x = min(balls)
        balls.remove(x)
        print(x)

C - King's Summit

まず、集合地点をどこに設定するかですが、全員の中点を選べば間違いなさそうです。X方向とY方向でそれぞれ中点を求めます。中点は平均ではなく、X方向Y方向それぞれ最大値と最小値の中点にします。

---

次に、移動についてです。

「人は8近傍のマスに移動する」なので、斜め方向にも移動することができます。斜め方向への移動はX座標とY座標の両方を変えるのでお得です。

ですので、ある人が移動する距離は、X座標とY座標の差の大きい方を選べば良いです。これを全員に対して計算し、最大値を求めればOKです。

INF = 10 ** 18

N = int(input())
points = []
min_r = INF
max_r = -INF
min_c = INF
max_c = -INF

# R, Cの座標を取得 & 最小値・最大値を更新
for i in range(N):
    R, C = map(int, input().split())
    points.append((R, C))
    min_r = min(min_r, R)
    max_r = max(max_r, R)
    min_c = min(min_c, C)
    max_c = max(max_c, C)

# 中心点(集合地点)を求める
center_r = (min_r + max_r) // 2
center_c = (min_c + max_c) // 2

# 各人が集合地点まで移動する時間を計算
max_time = 0
for i in range(N):
    R, C = points[i]
    time_r = 0 ＃ R座標の移動時間
    time_c = 0 ＃ C座標の移動時間
    if R > center_r:
        time_r = R - center_r
    else:
        time_r = center_r - R
    if C > center_c:
        time_c = C - center_c
    else:
        time_c = center_c - C

    # 斜め方向への移動を考慮して、移動時間を調整
    # なんか難しい計算をしていますが... 実は time = max(time_r, time_c) で十分です。
    time = 0
    if time_r > time_c:
        diff = time_r - time_c
        time = (time_r + time_c - diff) // 2 + diff
    else:
        diff = time_c - time_r
        time = (time_c + time_r - diff) // 2 + diff

    # 最大時間を更新
    max_time = max(max_time, time)

print(max_time)

D - Substr Swap

文字列を入れ替える問題です。

M回の入れ替え操作を素直に行うと、TLEしてしまいそうです。

---

ある位置iの文字について、以下のように考えます。

• 偶数回入れ替えた → 文字 S[i] を採用
• 奇数回入れ替えた → 文字 T[i] を採用

ということで、各位置の入れ替え回数をカウントできれば良いとわかります。

---

入れ替え回数のカウントには、累積和の考え方を使います。

例えば、(L, R) = (2, 4) なら

[0 1 0 0 -1 0] という配列を作ります(Lの位置で+1、R+1の位置で-1 している)。

↑の累積和で計算すると、以下のようになり、各位置の入れ替え回数がわかります。
[0 1 1 1 0 0]

N, M = map(int, input().split())
S = input()
T = input()

# 入れ替え回数をカウントする配列を初期化
counter = [0] * (N + 2)
for i in range(M):
    L, R = map(int, input().split())
    counter[L] += 1
    counter[R + 1] -= 1

answer = []
current = 0 # 累積和の初期値
for i in range(1, N + 1):
    current += counter[i] # 累積和を更新

    # 偶数回なら S[i-1]、奇数回なら T[i-1] を採用
    if current % 2 == 0:
        answer.append(S[i - 1])
    else:
        answer.append(T[i - 1])

print(''.join(answer))