ABC153

AtCorder Beginner Contest 153 にバーチャル参加しました。
ABCDの4問ACでした。
Python3を使用しています。

A問題

モンスターの体力が何回の攻撃で 0 以下になるかを考えるので、割り算の商を求める必要があると考えます。
しかし、回数は整数でないとおかしいため、割り算の商が小数を取った場合は繰り上げた整数を答える必要があります。

H, A = map(int,input().split())
if H % A == 0:
    print(H // A)
else:
    print(H // A + 1)

小数点切り上げだとif文も使わなくて良かった。

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

B問題

全ての必殺技で減らせる体力がモンスターの体力より大きければ勝つことができます。

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

C問題

モンスターの体力を 0 にする必殺技は、体力の大きいモンスターに使いたいと考えます。
そこでモンスターを体力の大きい順(降順)に並べ、 K 体のモンスターを必殺技で倒します。
残った N - K 体のモンスターは攻撃で倒すため、この N - K 体のモンスターの総合体力の回数だけ攻撃を行う必要があります。

N, K = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
del A[:K]
print(sum(A))

D問題

最初は体力 H のモンスターが 1 体いる、と問題文から読み取ります。
1 回の攻撃で体力が半分になったモンスターが 2 体になる(小数点以下の値は切り捨て)、という操作を繰り返します。
モンスターの体力 H が 2 の累乗でない場合、 H は約数に奇数を持ちます。
そのため体力を半分にする過程で小数点の切り捨てが起こり、モンスターが分裂するだけで、総合体力が減ります。
そこで、体力 H が 2 の累乗で攻撃回数に変化が起きるのではと考えました。

ここからは実際に数値計算し、一般論を導きます。

H 攻撃回数
1 1 回
2 ~ 3 3回
4 ~ 7 7回
8 ~ 15 15回
H が 2ⁿ から 2ⁿ⁺¹ - 1 のとき、攻撃回数は 2⁰ から 2ⁿ までの和で表せるということが分かります。

そこで、今度は H が 2 の n 乗と 2 の n + 1 乗 の間にあるかを考えます。
10 進数を 2 進数に変換して文字数を数えることで求めます。

H = int(input())
n = len(bin(H)) - 3
N = [2 ** i for i in range(n + 1)]
print(sum(N))

H が 2ⁿ から 2ⁿ⁺¹ - 1 のとき、攻撃回数は 2ⁿ⁺¹ - 1 で表せた。
さらに、底が 2 の log を取って小数点以下を切り捨てることで n が求められた。

import math
H = int(input())
n = math.floor(math.log2(H))
print(2 ** (n + 1) -1)

E問題

どうやら、個数制限ナップサックという有名な問題だったらしい。
DP(動的計画法)もさっぱり分からなかったので、こちらを参考にさせてもらいました。
分かりやすい。

まずTLEになった結果です。(Pypy3だとAC)
使える N 種類の魔法のうち、 i 番目の魔法について考えます。
i 番目の魔法を使って体力を合計で j 減らせる場合の消耗魔力は
dp[j] = dp[j - a] + b
i 番目の魔法を使わずに体力を合計で j 減らせる場合の消耗魔力は
dp[j] = dp[j]
となります。
これらを比較して、最小値を求めdp[j]とします。
モンスターの体力ぴったりで倒す必要はないため、dp[]の要素数はH + max(減らせる体力)となっています。
初期値はdp[0] = 0
また、0が最小値になってしまうためif文で場合分けしています。

H, N= map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
ma = max(A)
dp = [0] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        if dp[j] == 0:
            dp[j] = dp[j - a] + b
        else:
            dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))

二重のforループの中でif文は遅くなりそうだなと反省し改善したのですが、TLEです。(Pypy3だとAC)
dp[]の要素に無限大を入れて作っているので場合分けして判定しなくて良くなった。
見やすくなったけど、1 つ目の解答より時間はかかっている。

H, N= map(int,input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
ma = max(A)
dp = [float("inf")] * (H + ma)
dp[0] = 0
for i in range(N):
    a = A[i]
    b = B[i]
    for j in range(1, H + ma):
        dp[j] = min(dp[j - a] + b, dp[j])
print(min(dp[H:]))

PythonでACしたい。

F問題

ギンギツネは N 体のモンスターと戦っています。
モンスターは 1 列に並んでおり、数直線上にいるとみなすことができます。
i 番目のモンスターは座標 Xi にいて、体力は Hi です。
ギンギツネは爆弾を使ってモンスターを攻撃することができます。 座標 x で爆弾を使うと、座標が x−D 以上 x+D 以下の範囲にいる全てのモンスターの体力を A 減らすことができます。 爆弾を使う以外の方法でモンスターの体力を減らすことはできません。
全てのモンスターの体力を 0 以下にすればギンギツネの勝ちです。
ギンギツネがモンスターに勝つまでに爆弾を使う回数の最小値を求めてください。

サンプルだと正しい結果が出るんだけど、WAだった。
距離を昇順にならべて、一番小さい値が0になるまで攻撃する。
それで同時に攻撃される範囲のモンスターの体力を減らして、新たにリストを作り直すと考えた。

import math
N, D, A= map(int,input().split())
X = [0] * N
H = [0] * N
Y = []
for i in range(N):
    X[i], H[i] = map(int, input().split())
    Y.append([X[i] ,math.ceil(H[i] / A)])
Y.sort()
d = 0

while len(Y) > 0:
    y_min = Y[0][1]
    c = 0
    d += y_min
    for i in range(len(Y)):
        if Y[i][0] < Y[0][0] + 2 * D + 1:
            Y[i][1] = Y[i][1] - y_min
            if Y[i][1] <= 0:
                c += 1
    del Y[0:c]
print(d)