AtCoder ABC 426 解いてみた (PythonでABC問題)

ABC426を振り返ります

今回はUnratedで参加しました。
いまいち体調が良くなかったので仮眠していたところ、開始30分後に起きたためです...。
一定時間以上遅刻すると、Rated参加はできなくなるようです(仮に参加してもメリットはあまりないですね)

コンテスト時間内ではABまで2問の解答でした。C問題は時間内ではTLEが解決できず、解説を読んで正解しました。

この結果でRated参加だと厳しかったので、結果的に今回はUnrated良かったかもしれません。

A - OS Versions

あらかじめ ["Ocelot", "Serval", "Lynx"] の配列を作っておき、X, Yのindexを求めて、比較しました。

X, Y = input().split()

# X と Y の位置を求め、比較する
versions = ["Ocelot", "Serval", "Lynx"]
x_index = versions.index(X)
y_index = versions.index(Y)

print("Yes" if x_index >= y_index else "No")

B - The Odd One Out

文字列の中で1文字だけの文字を表示する問題です。
文字の出現回数を dict でカウントし、出現回数が1回のものを print するようにしました。

S = input()
s_dict = defaultdict(int)

for i in range(len(S)):
    s_dict[S[i]] += 1

for k in s_dict:
    if s_dict[k] == 1:
        print(k)
        exit()

C - Upgrade Required

「x 以下のバージョンを y にバージョンアップした」場合、x以下のバージョンは0台になるので、それ以降は台数をカウント必要はありません。

という性質を利用すると、次回以降のバージョンアップで台数を計算する際のループを減らすことができます。(x-1以下のバージョンの台数を調べなくて良いため)

N, Q = map(int, input().split())

# バージョンごとの台数を配列に保持。初期は1〜Nまで1台ずつある
versions = [0] * (N+1)
for i in range(1, N+1):
    versions[i] = 1

min_version = 1 # 現在存在している最低バージョン
for i in range(Q):
    X, Y = map(int, input().split())

    # すでにアプデ済のバージョンなら、0台
    if min_version > X:
        print(0)
        continue

    # 今回アプデする台数をカウント(バージョンが[min_version - X] の台数)
    up_count = 0 
    for j in range(min_version, X+1):
        up_count += versions[j]
        versions[j] = 0

    # アプした台数を表示
    print(up_count)

    # バージョンY の台数を増やす
    versions[Y] += up_count
    
    # 最低バージョンを記録
    min_version = X

最初はSortedSet を使用して解こうとしていたんですが、TLEになってしまい解けずでした。https://atcoder.jp/contests/abc426/submissions/69873718