PythonでAtCorder ABC260 (A,B,C)｜タムタムのアウトプット

先週末ののAtCorder ABC260、参加できずでした。もう何回連続で参加できていないのかわかりません。

260、やってみたところA,B,Cはできました。ただ、参加していたら本番中に溶けていたかどうかと言う怪しい感じがします。

先週末は予定はなかったのですが、土曜日でなく日曜日開催ということもあってか、AtCorderの存在そのものを忘れていました。家でゆっくり過ごしていて、AtCorderのことを思い出した頃は22時を回っていました。

Contents

【A】A Unique Letter
【B】
【C】Changing Jewels
【D】Draw Your Cards
まとめ

【A】A Unique Letter

S = input()

if S[0] != S and S[0] != S:
    print(S[0])
elif S != S[0] and S != S:
    print(S)
elif S != S[0] and S != S:
    print(S)
else:
    print(-1)

こんな感じです。他にもっといい書き方がある気もしますが、考えるのも面倒なので、これでいいやって感じで、次にいきました。

【B】

少し難しかった気もしますが、Bらしい問題という気もします。

やることはシンプルで愚直にコードを書いていく感じですね。何をやっているかコメントを丁寧に残していかないと、わけがわからなくなりそうでした。

結構、時間がかかりました。本番だったら、Bをやって時点で燃え尽きてそうな気がします。

PASSしたコードは以下。

N, X, Y, Z = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a_sort_idx = sorted(range(len(A)), key=lambda k: A[k], reverse=True)
b_sort_idx = sorted(range(len(B)), key=lambda k: B[k], reverse=True)


passed = []  # 合格者

# 数学 高得点X人
for a_i in a_sort_idx[:X]:
    passed.append(a_i + 1)

# 英語 高得点Y人、数学X人に入っているひとは除く
cnt_y = 0
y_idx = []  # 英語で合格した人のidx
for b_i in b_sort_idx:
    if b_i in a_sort_idx[:X]:
        continue  # 数学ですでに合格
    else:
        cnt_y += 1
        if cnt_y <= Y:
            y_idx.append(b_i)
            passed.append(b_i + 1)
        else:
            break

# 残りの人の数学、英語の合計点
z_score: dict = {}  # {受験者番号, 合計点}
for i in range(N):
    if i in a_sort_idx[:X] or i in y_idx:
        continue  # 既に合格済み
    else:
        z_score[i] = A[i] + B[i]

# 点数の高い順にsort
z_score_sort = sorted(z_score.items(), key=lambda x: x, reverse=True)
z_cnt = 0
for v in z_score_sort:
    z_cnt += 1
    if z_cnt <= Z:
        passed.append(v[0] + 1)
    else:
        break

print(*sorted(passed))

【C】Changing Jewels

C問題ではありますが、アルゴリズムなどはなく、B問題同様、素直にコードに落とし込んでいくだけという感じでしょうか。

紙の上で書きながら考えていたら混乱しましたが、とりあえずコードに落とし込みながら考えたらスッと解けました。

ただ早朝の頭のクリアな時間にやったらできましたが、本番の時間以内に回答にたどり着くのは無理な気がします。

PASSしたコードは以下。

N, X, Y = map(int, input().split())
# N, X, Y = 2, 3, 4
# N, X, Y = 1, 5, 5
# N, X, Y = 10, 5, 5


red, blue = {}, {}  # key: lv, value: stone count
for i in range(N):
    red[i + 1] = 0
    blue[i + 1] = 0
red[N] = 1

# lv:n -> lv: n-1
for i in range(N - 1):
    lv = N - i

    # red stone -> red: n-1 * 1 + blue: n * x
    red_count = red[lv]
    red[lv - 1] += red_count
    blue[lv] += red_count * X
    red[lv] = 0

    # blue stone ->red: n-1 * 1 + blue: n-1 * Y
    blue_count = blue[lv]
    red[lv - 1] += blue_count
    blue[lv - 1] += blue_count * Y
    blue[lv] = 0

print(blue)

【D】Draw Your Cards

問題を読んで、コードを書くことなく諦めました。Dは解けないという負け根性が染みついていて、すぐに諦めがちです😓

Nが2*10**5なので全探索でいけそうな気がしますが、ループ内で表のカードの配列も扱う必要があり、計算量があがるなと思いました。「P は (1,2,…,N) の順列 ( (1,2,…,N) を並べ替えて得られる列 ) である」という表記が味噌で、ループ内で何か特別なアルゴリズムを使う必要あるのかなと思って、着手せず😇

解説によると、C++では、この問題に適したデータ構造 set があるようです。Pythonでは標準機能ではなさそうで、第三者によるSortedSetというものがあるみたいですね。

と、ここまで調べて、止めました。