問題

https://atcoder.jp/contests/abc153/tasks/abc153_d

方針

計算量の都合上、シミュレーションを行うことはできない。
数学的な解法を考える。

ポイント

言葉だけで理解しようとするのは若干難しいため、記事の最後にあるシミュレーションを眺めながら読み解いていただきたい。

• 攻撃をすると、モンスターは体力が1でない限り倍々に増えていくためモンスターの数は常に2の累乗である。
  • つまり、攻撃の総回数はそれらの和であるため、2^N-1で表すことができる。
• 攻撃効率がもっとも良いのは攻撃のたびにモンスターの体力の和が攻撃前より1減ることである。
  • 全ての攻撃が効率がよくるのは、Hが2^N-1の場合であるとわかる。
  • また、攻撃回数がモンスターの体力Hを上回ることはない。
• そのため、2^N-1を満たす自然数を小さい順に数え、H以上の値が現れた時、その値が答えである。

コード

1
2
3
4
5

H = int(input())
for i in range(41):
    if (2**i-1 >= H):
        print (2**i-1)
        break

シミュレーション

下記のようなシミュレーション用のコードを書いてみた。

1
2
3
4
5
6
7
8

ls = [int(input())]
while(ls): # リストの要素が1以上であればtrue
    print (ls)
    new = []
    for e in ls:
        if e>1: # 体力が１であれば、新たなモンスターは出現しない
            new.extend([e//2, e//2])
    ls = new

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

>>> 6
[6]
[3, 3]
[1, 1, 1, 1]

>>> 7
[7]
[3, 3]
[1, 1, 1, 1]

>>> 8
[8]
[4, 4]
[2, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 1]

問題

https://atcoder.jp/contests/abc153/tasks/abc153_c

方針

体力の多いモンスターに対して、優先的に必殺技を使う

ポイント

• 組み込み関数sortを用いるとよい
  • 昇順にソートが行われる
• ソート済みのリストに対してスライスをし、合計を計算すれば良い
  • 小さい順（先頭から）にスライスを行う
    • N(モンスターの数)からK(必殺技を使える回数)を引いた数がスライスの位置（攻撃で倒す必要があるモンスターの数）となる
  • モンスターの数以上に必殺技を使える場合(N<=K)に注意する
    • 組み込み関数maxを用いることで、スライスの位置が0以上になることを保証できる

コード

1
2
3
4
5

N, K = map(int, input().split())
H = list(map(int, input().split()))
H.sort()
idx = max(N-K,0)
print (sum(H[:idx]))

メモ

組み込み関数sortedを用いた場合、ソートされたリストが返却される。

一方、メソッドsortをコールした場合、元のリストがソートされる。

このような上書きされる処理をインプレースな処理と呼ぶ。返却値はない(None)であることに注意する。

1
2
3
4
5
6

>>> ls = [1, 4, 5, 3, 2]
>>> sorted(ls) # ソートされたリストが返却される
[1, 2, 3, 4, 5]
>>> ls.sort() # インプレースに変更する。この場合は値の返却はない
>>> ls
[1, 2, 3, 4, 5]

発展

PythonのソートアルゴリズムにはTimsortが用いられている。平均計算量、最悪計算量ともにO(nlogn)である。

問題

https://atcoder.jp/contests/abc153/tasks/abc153_b

方針

必殺技で減らすことができる体力を、全ての必殺技について足し合わせればよい。

ポイント

組み込み関数sumを用いるとよい。

コード

1
2
3
4
5
6

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

発展

組み込み関数sumはlistだけでなく、set, tuple, dictに対しても使うことができる。

1
2
3
4
5
6

>>> sum({1,2,3})
6
>>> sum((1,2,3))
6
>>> sum({1: "one", 2: "two", 3: "three"})
6

問題

https://atcoder.jp/contests/abc153/tasks/abc153_a

方針

HをAで割って切り上げを行えばよい。

ポイント

Pythonでは切り捨て除算//は存在するが、切り上げ除算は存在しない。
そこで下記のコードのように実装する。数式のイメージとしては

1. 先ずは、切り捨て除算を考える
2. 分子に分母を足すことで、切り上げ処理にする
3. 境界値（割り切れるケース）の調整をする

といったところである。

コード

1
2

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