ABC370 感想まとめ

トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370） - AtCoder

ABCまで3解答でした。パフォーマンス831でレーティングは776 (+7)になりました。

前回の復習(AtCoder ABC369 振り返り感想戦)はお試しでSwiftを使いましたけども、今回は準備期間がなく、いつものPythonで参加でした。

今回は昼間に日本酒を結構飲んでおり、若干アルコールが残る中での参加でしたが、まあまあの成績が取れてよかったです。(以前同じことをして、成績が悪かったので決して勧められるものではない...)

万全であれば、D問題をもう少し頑張れた気がするので、SortedSetなどを復習して次回以降に備えたいと思います。

A - Raise Both Hands

if文で判定しました。

L, R = map(int, input().split())
if L == 1 and R == 0:
    print("Yes")
elif L == 0 and R == 1:
    print("No")
else:
    print("Invalid")

B - Binary Alchemy

変換用の2次元配列を作って、変換していきました。

N = int(input())

# 変換用の2次元配列Aを作成する
A = [[0] * (N + 10) for _ in range(N + 10)]
for i in range(N):
    line = list(map(int, input().split()))
    for j in range(len(line)):
        A[i+1][j+1] = line[j]

# 配列Aを利用して、元素を合成していく
genso = 1
for g in range(1, N+1):
    genso1 = genso
    genso2 = g
    if genso1 >= genso2:
        genso = A[genso1][genso2]
    else:
        genso = A[genso2][genso1]

print(genso)

C - Word Ladder

以下の手順で求めました。

手順1:文字列の最初→最後まで走査して、辞書順で先になる文字(E→Aとか)のみを変換する
手順2:文字列の最後→最初まで走査して、辞書順で後になる文字(A→Eとか)のみを変換する

これで、置換文字列を辞書順に求められます。

早ときは苦手なのですが、この問題は解法がすっと浮かんで、自分としては早く解答できたと思います。

S = input()
T = input()

# アルファベットのリスト["a","b","c", .... ,"z"]
alphabet = list(string.ascii_lowercase)

# S, T を一文字づつ比較し、フラグを求める
# 0=一致, -1=辞書順で早い, 1=辞書順で遅い
flag = [0] * len(S)
for i in range(len(S)):
    if S[i] == T[i]:
        continue
    s = alphabet.index(S[i])
    t = alphabet.index(T[i])
    if s < t:
        flag[i] = 1
    else:
        flag[i] = -1
X = []

# 手順1：先頭から走査して、辞書順が早くなる文字を置換
for i in range(len(S)):
    if flag[i] == 0:
        continue
    if flag[i] == -1:
        S = S[:i] + T[i] + S[i + 1:]
        X.append(S)

# 手順2：末尾から走査して、辞書順が遅くなる文字を置換
for i in range(len(S) - 1, -1, -1):
    if flag[i] == 0:
        continue
    if flag[i] == 1:
        S = S[:i] + T[i] + S[i + 1:]
        X.append(S)

print(len(X))
for x in X:
    print(x)

公式解説のように、「とりあえず置換できる箇所を全部置換してみて、辞書順の先頭を求める」という方法もありですね。

D - Cross Explosion

普通にやったらTLEなので、2分探索で爆発により壊される壁を求めるというのはわかった。
壁のある無しの状態をフェニック木で管理しようとして、実装が面倒なことになり完成できず...。
公式解説によれば、壁情報はSortedSetで管理すると良いらしい。なるほど。