ABC 388感想まとめ

ABC387はABCDの4問出来ました。

コンテスト中は4問解けて上出来...と手応えを感じていたのですけども、意外と順位が普通でちょっと意外でした。どうも、それほど問題の難易度が高くなかったようです。

A - ?UPC

Sの1文字目と、"UPC" をくっつけた文字列を出力します。

S = input()
answer = S[0] + "UPC"
print(answer)

B - Heavy Snake

1〜D までの各k について、素直に重さ = T * (L+k) を計算して、最大の重さを求めています。

N, D = map(int, input().split())
TL = []
for i in range(N):
    T, L = map(int, input().split())
    TL.append((T, L))

answers = []
# 1〜D までの k について調べる
for k in range(1, D+1):
    # + k の場合、各ヘビの重さの中で最大のものを求める
    max_weight = 0
    for i in range(N):
        T, L = TL[i]
        max_weight = max(max_weight, T * (L+k))
    answers.append(max_weight)

for answer in answers:
    print(answer)

C - Various Kagamimochi

A1 が上の餅の場合、下に置ける餅は何個？
A2 が上の餅の場合、下に置ける餅は何個？
...
AN が上の餅の場合、下に置ける餅は何個？

というのを、A1-ANまで求めます。

「A1の下に置ける餅の数 == 配列Aの中で、サイズが A1 * 2 以上の餅の数」になります。
これを効率的に求めるには、2分探索で A1*2 以上になる位置を探すとよいでしょう。

import bisect

N = int(input())
A = list(map(int, input().split()))

count = 0
for i in range(N):
    smaller = A[i]
    bigger = A[i] * 2

    # 二分探索で、下に置ける餅の数を求める
    bigger_index = bisect.bisect_left(A, bigger)
    if bigger_index == N:
        continue
    count += N - bigger_index
print(count)

D - Coming of Age Celebration

これは結構ややこしい問題でした。

考え方は、

「i番目に成人した宇宙人は、その後の(i+1)〜N までの宇宙人に 1個ずつ石を配る」

という風に、「成人したときに自分の持っている石を配るだけ配る」と考えると、問題が単純化出来ます。

i番目に成人した宇宙人が持っている石の個数は、以下です。

元々持っていた個数 + 他の人からもらった個数

他の人からもらった個数は、SegTreeと累積和(いもす法？)で管理しました。

SegTree を久々に使ったので、使い方を調べるのに時間がかかってしまいました。
解説の感じでは、別にSegTreeを使わなくても解けるので、そのあたりは今後の課題ですね...。

from atcoder.segtree import SegTree

N = int(input())
A = list(map(int, input().split()))

# サイズ N、初期値 0 の SegTreeを準備
def sum_op(x, y):
    return x + y
st = SegTree(sum_op, 0, N)

answer = [0] * N
for i in range(N):
    # i 番目の石の数 = A[i] + SegT[]
    current = A[i] + st.prod(0, i+1) 

    # 以降の宇宙人に配る数
    send_count = min(current, max(N - i - 1, 0))

    # 配ったあとの数
    answer[i] = current - send_count

    # 配る(差分だけ管理)
    if i < N - 1 and send_count > 0:
        # 次の人はSegTreeを +1
        st.set(i+1, st.get(i+1) + 1)

        # 配列の最後まで配れきれない場合、配れない区切りでSegTreeを-1にする
        if i + send_count + 1 < N:
            st.set(i + send_count + 1, st.get(i+send_count + 1) -1)

print(*answer)

E - Simultaneous Kagamimochi (解説AC)

これは解説動画と公式解説を見てACしました。

コンテスト中は解説動画の中で「駄目な貪欲法」と言われている方法で考えていて、正解にたどり着けずでした...。「貪欲法を使うときは、答えが求まると確認すること」というのを今後気をつけていきたいと思います。

N = int(input())
A = list(map(int, input().split()))

used = set()
count = 0

left = 0
right = N // 2 + 1

# k個の鏡餅を作れるか
def can_create(k):
    for i in range(k):
        smaller = A[i]
        learger = A[N - k + i]
        if smaller * 2 > learger:
            return False
    return True

# 二分探索でmaxの数を探す
while right - left > 1:
    mid = (left + right) // 2
    if can_create(mid):
        left = mid
    else:
        right = mid

print(left)