【AtCoder 緑色を目指して】ABC368【競技プログラミング】

技術ブログ 競技プログラミング

はじめに

こんにちは、駒嶺です。今回はAtCoder Beginner Contest 368の所感です。
今回もPythonで解いていきます。

A – Cut

カードの山の下からのK枚を順序を保ったまま山の一番上に乗せます。

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

A = A[N-K:] + A[:N-K]
print(*A)

リストのスライスでその通りに表現できますね。

B – Decrease 2 max elements

整数列Aの1番目に大きい数と2番目に大きい数を-1する。
という操作を何回繰り返せば正の要素の個数が1つ以下になるでしょうか？

解答（コンテスト終了後）

import heapq

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

A = [-i for i in A if i > 0]
heapq.heapify(A)
cnt = 0
while len(A) > 1:
    cnt += 1
    a = heapq.heappop(A)
    b = heapq.heappop(A)
    if (a := a + 1) < 0:
        heapq.heappush(A,a)
    if (b := b + 1) < 0:
        heapq.heappush(A,b)

print(cnt)

大苦戦しました。コンテスト中は先にC問題を解いてからB問題に戻りましたが時間内には間に合いませんでした。
私の回答ではheapq（優先度付きキュー）まで取り出していますが、なんとこの問題は問題文の通りに毎回ソートし1つ目の要素と2つ目の要素から-1する操作を実装するだけで制限時間以内に収まります。
計算量の計算を怠って変に工夫しようとした結果ドツボにはまりました。

C – Triple Attack

体力Hiの敵がN人並んでいます。前から順番に倒していって何回攻撃すればすべての敵を倒しきるでしょうか？
攻撃は1,1,3と基本攻撃力1ですが3回ごとに攻撃力が3になります。

解答

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


T = 0
for Hi in H:
    low = -1
    high = Hi
    while low + 1 < high:
        num = (low + high) // 2
        Triple = (num + (T % 3)) // 3
        if num + Triple * 2 >= Hi:
            high = num
        else:
            low = num
    T += high

print(T)

攻撃回数で二分探索をしました。
攻撃力が3になるタイミングは3で割ったあまりで計算しています。
実際は二分探索などする必要はなかったのですが、攻撃するごとに攻撃力が1ずつ増えていくと勘違いをしていた名残でこんな実装になりました。まさか平均攻撃力5/3の攻撃で体力最大2×10^5の敵を倒しきるとは…

コンテスト結果

今回も振るわない結果になりました。A問題とC問題の2完だったのでもっと酷い結果になると思っていましたが思ったよりはマシでした。
次回こそはいい結果を残したいと思います。

おわりに

次回はABC369の記事を投稿します。
本ブログを通じて私と一緒に競技プログラミングの世界を楽しんでいただければ幸いです。
また、各種ご支援させていただきますので、お気軽に「お問い合わせフォーム」よりお問い合わせください。

お問い合わせ
　業務実績　

関連記事