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で管理すると良いらしい。なるほど。