ABC373 感想まとめ
AtCoder Beginner Contest 373 - AtCoder
Rated参加し、D問題まで4解答でした。パフォーマンス 1098 で、レーティング 775 → 813 (+38)でした。7/13以来、2ヶ月半ぶりの緑色復帰です。
緑色に復帰したので、この振り返りのタイトルも「ほぼ緑コーダーが...」から「緑コーダーが...」に変更しました。
目先のレーティングには一喜一憂しないようにしているとはいえ、自分の名前のところが緑色になるとやはり嬉しくなってしまいます。
E問題は解けそうで解けなくて、諦めそうになりつつ時間切れまで考えていました。解説を見ていると思っていたよりも難しく、結局今の実力では及ばないレベルでした。しかし、諦めずに考えたメンタル力が、今後どこかで役に立てばいいなと思っていたりします。
A - September
12行の文字列を読み込み、文字数をチェックします。
9月のSeptemberは9文字だなと、この問題で初めて意識しました。問題作った人はよく気づいたなあ。
count = 0
for i in range(12):
S = input()
if len(S) == i+1:
count += 1
print(count)
B - 1D Keyboard
ABCDEFG...XYZ の配列を用意して、文字列Sの中でABC...の位置を順番に求めました。
S = list(input())
pos = S.index('A')
alphabet = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
answer = 0
for i in range(len(alphabet)):
# 次に探す文字
alpha = alphabet[i]
# Sの中で文字の位置を
next_pos = S.index(alpha)
answer += abs(next_pos - pos)
pos = next_pos
print(answer)
C - Max Ai+Bj
Pythonでは max(list) でリストの最大値を求められるので、それを利用しています。
C問題としては難易度が低く、difficulty75でした。普段と比べて簡単だったので「何か罠があるのでは...」と考えて、提出前に念入りに確認した人が多かったようです。私もそうでした。
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
max_a = max(A)
max_b = max(B)
print(max_a + max_b)
D - Hidden Weights
「u→vにコスト w で移動できる」
ということは、
「v→uにコスト -w で移動できる」
も成り立つことに気づくと、問題の理解が簡単になった。
頂点 1...N に対して、幅優先探索で行けるところまで行き、コストXを求める...という方針で求めました。
各頂点のコストは0で初期化しております。
N, M = map(int, input().split())
node = defaultdict(list)
for i in range(M):
u, v, w = map(int, input().split())
node[u].append((v, w))
node[v].append((u, -w)) # マイナス w 払えば、逆方向に行ける
visited = [False] * (N + 1) # 訪れた頂点フラグ
x = [0] * (N + 1) # 各頂点への移動コスト(default=0)
# 頂点 1...N から
for i in range(1, N + 1):
# すでに訪問済ならスルー
if visited[i]:
continue
# スタート位置 i を訪問済にする
visited[i] = True
# 頂点 i から行けるところを幅優先探索
q = deque([i])
while q:
cur = q.popleft()
for next, w in node[cur]:
if visited[next]:
# 訪問済ならスルー
continue
else:
# 行けるところは コストx と visitedフラグ を設定
x[next] = x[cur] + w
visited[next] = True
q.append(next)
print(*x[1:])