AtCoder ABC382 PythonでA〜Cを復習

ABC382 感想まとめ

今週は色々あって忙しく、ABC382コンテスト本番から６日後の金曜日にようやく復習できました。

• C問題が配点350となっていて、いつもよりも難しいのでは...と思いながら解いていたのですけど、difficulty 476でそうでもないのでした
• D問題は問題を読んで「難しそう」と思い未着手で終わったのですけど、こちらもdifficulty 685 で、D問題としてはそこまででもない難易度でした

ちょっと今回は、最近の練習不足が表に出てしまった感じですね...。

A - Daily Cookie

クッキーを食べる数をカウントして、食べた数だけ空き箱が増える...という方針です。

N, D = map(int, input().split())
S = input()

cookie_count = 0 # クッキーの数
empty_count = 0  # 空箱の数

for i in range(N):
    if S[i] == '@':
        cookie_count += 1
    else:
        empty_count += 1

# 食べた数をカウント
if D > cookie_count:
    eat_count = cookie_count
else:
    eat_count = D

print(empty_count + eat_count)

問題文 @ は D個以上含まれる という条件を見落としていて、その場合の対応処理を書いていたので、もう少し簡単に書けそうです。

B - Daily Cookie 2

文字列Sの右から、Dの数だけ '@' を '.' に置き換えます。

N, D = map(int, input().split())
S = list(input())

eat_count = 0

# 文字列の右側からチェック
for i in range(N-1, -1, -1):
    # '@' を '.' に置き換え
    if S[i] == '@':
        S[i] = '.'
        eat_count += 1

    # D 回置き換えたら終了
    if D == eat_count:
        break

print(''.join(S))

C - Kaiten Sushi

この問題はソースコードの実装量が多くなってしまい、難しかった。
方針は以下のようにしました。

１. Aを左から見ていって、その時点での最小値の配列を求める

A = [3 8 2] なら、[3 3 2]

２. 重複しているところを省略する。また、美食度:indexのdictを作る

[3 3 2] → [3, 2] (サンプルでは min_a_list )

{3 : 0, 2 : 2} (サンプルでは value_to_index )
美食度3の人は index=0 にいる。美食度2の人は index=2 にいる。という情報。

３．Bの各値(美味しさ) について、Aの中のどの人に食べられるのかを求める
　3.1 min_a_list を２分探索して、どの美食度の人に食べられるかを調べる
　3.2 value_to_index をつかって、美食度の人がどの位置にいるかを調べる

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

min_a = min(A) # A内の最小値

min_a_list = [] # Aを左から見ていったときの、最小値の配列
min_a_list.append(A[0])
value_to_index = {A[0]: 0} # {美食度 : index} の dict
current_min = A[0] # 現在の最小値
for i in range(1, N):
    if A[i] < current_min:
        current_min = A[i]
        min_a_list.append(A[i])
        value_to_index[A[i]] = i

# 配列を反転
min_a_list.reverse()

answers = []
for i in range(len(B)):
    b = B[i]
    
    # bがAの最小値未満なら、-1
    if b < min_a:
        answers.append(-1)
        continue

    # 二分探索で、食べる人の位置を検索
    index = bisect.bisect_right(min_a_list, b)

    # value = 食べる人の美食度
    value = 0 
    if index == 0:
        value = min_a_list[0]
    else:
        value = min_a_list[index-1]

    # 美食度valueを、Aのindexに変換して、格納
    answers.append(value_to_index[value] + 1)

print('\n'.join(map(str, answers)))