AtCoder Beginner Contest 153の復習, E問まで(Python)

フレンズ回。

競プロ初心者の復習用記事です。

ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。

A - Serval vs Monster

攻撃力Aで体力Hを削るのに必要な攻撃回数を答える問題です。

H/Aの切り上げが答えとなります。切り上げ処理にはmath.ceil()を使用しました。

import math
H, A = map(int, input().split())
print(math.ceil(H/A))

ちなみにmath.ceil()は数が大きすぎる時に誤差が出うると聞きました。(H+A-1)//Aみたいな書き方でもいいんですが、なんか気に入らなかったので軽く調べました。

この記事で紹介されている以下の書き方がスマートかもしれません。

H, A = map(int, input().split())
print(-(-H//A))

-(-H//A)という書き方。負の数での切り捨て処理は-0.1→-1、というように切り上げと同等の処理になるようです。そういえばこの書き方他の解答でも見たことあります。今後はできるだけこれを使うようにしましょうか。

B - Common Raccoon vs Monster

威力$A_i$の技を駆使して体力$H$を削り切ることができるか答える問題です。

必殺技の合計値が体力以上なら'Yes'を出力します。

H, N = map(int, input().split())
A = list(map(int, input().split()))
if H <= sum(A):
  print('Yes')
else:
  print('No')

C - Fennec vs Monster

「1ダメージを与える」(回数無制限)と「即死させる」(K回まで)の技を駆使してモンスターたちを倒す時、通常攻撃の回数を答える問題です。

モンスターのHPを順番に並べかえて、高い順にK体のモンスターは除外。残りのHPを合計した数が答えとなります。

NよりKの回数の方が多い場合があるので注意しましょう(一敗)。

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

H.sort()

print(sum(H[:max(N-K, 0)]))

追記:
pythonで配列のインデックスにマイナスの値を取ると特別な挙動をします。

a = [0, 1]
print(a[2:]) # はみ出たインデックスはスルーされる
# []
print(a[-1:]) # はみ出たインデックスは逆向きに数えられる
# [1]

この仕様を回避するためにmaxの処理を入れましたが、以下の書き方ならNとKの比較は必要なくなりますね。

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

H.sort(reverse=True)

print(sum(H[K:]))

D - Caracal vs Monster

攻撃するとHPが半分になって(切り捨て)分裂するモンスターに必要な攻撃回数を答える問題です。

数を置き換える

まず、HPは必ず切り捨て処理を行うことから与えられた値$H$は$2^{k-1}$(ただし$2^{k-1} \leq H < 2^k$)と変換しても同じ回数になります。

攻撃回数を考える

というわけで$2^{k-1}$のHPを持つモンスターに対しての攻撃回数を数えてみましょう。

まずHPが$2^{k-1}$を持つ1体のモンスターを攻撃します。これで1回。

次にHPが$2^{k-2}$を持つ2体のモンスター。これが2回。

次は$2^{k-3}$を持つ$2^2$体のモンスター、これが$2^2$回。

...

これを繰り返し、最終的にHP1を持つ$2^{k-1}$体のモンスターを$2^{k-1}$回殴ったところで勝利となります。

数式にしてみましょう。

$$ x = 1 + 2 + 2^2 + \cdots + 2^{k-1} $$
$$ = 2^k - 1 $$

ここの変換をちゃんと追うなら等比数列の和の公式とか使ってみてください。

というわけで

「値を$2^{k-1}$に置き換えて」「$2^{k}-1$を出力する」ことで答えが出せます。以下にコードを書きました。

H = int(input())

k = 0
while H:
  H //= 2
  k += 1
print(2**k-1)

E - Crested Ibis vs Monster

魔法の威力$A_i$と消費魔力$B_i$が渡されます。与えられたHを削りきるための可能な限り少ない消費魔力を答える問題です。

シンプルなDPで提出したら通りました。HPの値ごとに最小の消費魔力を配列に格納し、最小値を順番に更新していくだけ。動的計画法にも慣れてきました。

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

magic = [tuple(map(int, input().split())) for _ in range(N)]

DP = [0] + [10**9]*H

for h in range(H):
  for damage, mp in magic:
    DP[min(h + damage, H)] = min(DP[min(h + damage, H)], DP[h] + mp)
print(DP[H])

ただしこれを通したのはPyPy3のみで、Python3の方ではTLEが出ました。pythonならどうしたものかと見てみると、内包表記を利用して高速化している解答がありました。書き直してみます。

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

magic = [tuple(map(int, input().split())) for _ in range(N)]

DP = [0] * (H+10**4)

for h in range(1, H+1):
  DP[h] = min(DP[h - damage] + mp for damage, mp in magic)
print(DP[H])

先ほどのコードとはforで回しているhの意味が異なるのには注意。これでpythonでも通りました。

この記事はここまでとします。過去のコンテストとはいえ、自力でE問まで解けたのは初めてでうれしいです。