ABC419の感想戦

このところAtcode Beginner Contest (ABC)でAとB問題しか正解できない回が続いていただ、ABC419で久しぶりにAからD問題を正解できた。ここでは、その回答を振り返る。

A - AtCoder Language

問題：A - AtCoder Language

英単語が与えられるので、知っている単語であれば指定の文字列を返し、知らない単語であればUnknownを返す問題。

考え方

与えられる単語は全て小文字で、部分一致を考える必要がない。そのため単純に知っている単語カ比較して、一致していれば指定の文字列を返すだけ。

技術的工夫

コンテスト内では if - elif - elseを使ったが、match - caseを使ったほうがスッキリする。

S = input()

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

match - caseを使った場合。

S = input()

match S:
    case "red":
        print("SSS")
    case "blue":
        print("FFF")
    case "green":
        print("MMM")
    case _:
        print("Unknown")

Copilotによる謎の提案

コンテスト終了後にyellowという単語に対してRRRを返すコードが入っていると不正解になるテスト・ケースが含まれているという話がX上のメッセージにあった。これはAIにコードを書かせると生成されるという話もある。¹。

実際にVSCodeでもCopilotの補完機能を有効になっているとredからgreenのif-elifを書いた時にyellowが補完された。

B - Get Min

問題：B - Get Min

２種類のqueryが与えられ、その結果を返す問題。

• 1の場合は、指定の数字を袋に入れる。
• 2の場合は、袋に入っている最小の数を取り出して印刷する、

考え方

queryの数は最大でも100なので、特に工夫をする必要はない。

配列にquery1で与えられる数字を詰めていく。query2が来たら、最小の数を探して取り除く。

技術的工夫

pythonで配列から指定の項を削除するには、2種類ある。

• 配列の位置を指定する場合は、pop(index)を使用する。
• 値を指定する場合には、remove(value)を使用する。同じ値が複数ある場合は、そのうちの１つだけ削除する。

Q = int(input())

x = []
for _ in range(Q):
    query = list(map(int, input().split()))

    if query[0] == 1:
        x.append(query[1])
    elif query[0] == 2:
        ans = min(x)
        print(ans)
        x.remove(ans)

C - King’s Summit

問題：C - King’s Summit

\(10^9 \times 10^9\)のマス目があり、そこに\(N\)人の王様が散らばっている。全員が同じ場所に集まるのに必要な最小のステップ数を答える問題。ただし王様は、将棋の王と同じく上下左右に加えて斜めにも移動できる。

考え方

一番早く集まっる場所を考えると、全員の中心に集まるのが最短となる。

しかし中心ということで全ての王様の位置の平均を考えたが、これでは場所に偏りがあった時に最小のステップ数にはならない。例えば1次元で1,2,19にいた時、10に集まるならば9ステップで済むところ、平均だと7.3に集まることになり12ステップ以上必要になる。

そこで、全ての王様が集まっている状態を考えて、そこから元の位置に戻る最小のステップが求められていると考えた。そうすると、一番離れている２人の王様間の中心から移動するのが最短になる。

理解

最小のステップ

• 王様は斜めに進めるので、縦と横を独立に考えて位置を決められる。
• 一番離れている2人の王様は、マス目の値で最大と最小の位置にいる王様が該当する。
• よって中心から縦に移動するステップ数と、横に移動するステップ数の内、より大きいほうが真の最小ステップ数となる。

中心の決定

中心を考える時に、一番離れている王様間の平均をとるために2で割ったが、奇数離れていると、中心が.5になってしまう。そこで//で整数での割り算にした。

コンテスト時にはこれで良いのか自信がなかった。しかし改めて考えると、例えば\(1\)と\(4\)の計算での中心が\(2.5\)となった場合に、\(2\)を採用しても\(3\)を採用して、もともに最小は\(2\)となり最小ステップに変わりがないことに気がついた。

N = int(input())

min_x = 10 ** 9
max_x = 0
min_y = 10 ** 9
max_y = 0
persons = []
for _ in range(N):
    x, y = map(int, input().split())
    persons.append((x, y))

    if x < min_x:
        min_x = x
    if x > max_x:
        max_x = x
    if y < min_y:
        min_y = y
    if y > max_y:
        max_y = y

mean_x = (min_x + max_x) // 2
mean_y = (min_y + max_y) // 2

max_distance = 0
for x, y in persons:
    delta_x = abs(x - mean_x)
    delta_y = abs(y - mean_y)
    if delta_x > delta_y:
        distance = delta_x
    else:
        distance = delta_y

    if distance > max_distance:
        max_distance = distance
print(max_distance)

D - Substr Swap

問題：D - Substr Swap

\(S\)と\(T\) の文字列が与えられる。この\(S\)と\(T\)の間で組み換えを行い、最終的な\(S\)の文字列を答える問題。

考え方

実際に文字列の操作をしていたら計算時間を超えてしまうことが目に見えている。

そこで、文字列の操作をするのではなく、ABC408のC問題で使ったimos法で組み換えが起きた場所を記録するを採用した。

理解

• 組み換えが起こった位置を考える時に、問題文では\(R\)文字目から\(L\)文字目となっているが、組み換えが起こるのは、\(R-1\)と\(R\)の間と、\(L\)と\(L+1\)の間で起きていることに注意する。
• 端から見て行き、奇数ならばそこから先は組み換えの結果文字列\(T\)に由来する、偶数ならば文字列\(S\)に由来する。

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

selector = [0] * (N+1)
for _ in range(M):
    L, R = map(int, input().split())
    selector[L - 1] += 1
    selector[R] -= 1

index = 0
ans = []
for i in range(N):
    index += selector[i]
    if index % 2 == 0:
        ans.append(S[i])
    else:
        ans.append(T[i])
print("".join(ans))