ABC 085

AtCoder Beginner Contest 085 - AtCoder

C - Otoshidama

問題

10000円札、5000円札、1000円札があわせて $N$ 枚あり、金額は $Y$ 円だという
$N,Y$ の条件を満たす10000円札、5000円札、1000円札の枚数の組み合わせがあるか判定し、ある場合は一例を示せ

例

$N=1000, Y=1234000$ のとき、たとえば10000円札、5000円札、1000円札がそれぞれ14枚、27枚、959枚あれば、合計1000枚で

$10000*14+5000*27+1000*959=1234000$

となり、条件を満たす。また、26枚、0枚、974枚でも条件を満たす。どれを答えてもよい。

解法

O(N^2)

$1 \le N \le 2000$ なので、全部調べればいける

10000円札を0枚～N枚まで増やして調べる（x枚とする）
- 使える残り(y+z)は N-x 枚
- 5000円札を0枚～N-x枚まで増やして調べる（y枚とする）
  - 1000円札の枚数が自動的に決まる（N-x-y 枚）
  - これが $Y$ 円になるか調べる

# 擬似コード

for x in 0 .. N:
    for y in 0 .. N-x:
        if 10000 * x + 5000 * y + 1000 * (N-x-y) == Y:
            # 発見！
            
# ループ終了まで発見できない場合、NとYが不可能な組み合わせである

O(N)

鶴亀算の要領で差分を利用すると、計算量を減らせる

とりあえず $N$ 枚全部1000円だったとすると、 $1000N$ 円になる
実際の金額との差分を出す（ $diff = Y - 1000N$ ）
- この差分は、1000円札を1枚10000円札に替えると9000円、5000円札に替えると4000円減る
- つまり、 $diff = 9000x + 4000y$
- ただし、 $0 \le x, 0 \le y, x+y \le N$

あとは、この $x,y$ を1つずつ調べればよい。

        
          
          
              
              def solve(n, y):
    tmp1000 = n * 1000
    if tmp1000 > y:
        return -1, -1, -1
    diff = y - tmp1000
    for y in range(diff // 4000 + 1):
        tmp5000 = y * 4000
        if diff - tmp5000 < 0:
            break
        if (diff - tmp5000) % 9000 == 0:
            x = (diff - tmp5000) // 9000
            if x >= 0 and x + y <= n:
                return x, y, n - x - y
    return -1, -1, -1
 
print(*solve(*map(int, input().split())))

            

        
      

O(1)

連立方程式から考えると、 $O(1)$ で解ける。解説放送参照。

$Y'=Y/1000$ として、

$\begin{eqnarray} x+y+z &=& N \\ 10x+5y+z &=& Y' \end{eqnarray}$

ここから、 $x,y,z$ が非負整数という条件より、3つの条件式ができる。この条件式を満たす $z$ さえ見つければ、そこから求められる $x,y$ は必ず条件を満たしている。

$0 \le z \le min(N,Y) \\ Y'-z は 5 の倍数 \\ N-z \le \frac{Y'-z}{5} \le 2(N-z)$

一番下は、整理すると以下になる。

$\frac{5N-Y'}{4} \le z \le \frac{10N-Y'}{9}$

たとえば、 $N=1000,Y=1234000$ なら、

$0 \le z \le min(1000, 1234) = 1000 \\ z \equiv 4 \mod 5 \\ \frac{5000-1234}{4} = 941.5 \le z \le 974 = \frac{10000-1234}{9}$

となり、 $z=944,949,954, ...$ で解を持つことが分かる。

ただ、計算量的に十分間に合うなら、競技プログラミングでは考察・実装にかかる時間が短い方を選択するべきなので、最初の方法でいい。

D - Katana Thrower

問題

刀が $N$ 本あり、ヒットポイント $H$ の1匹の魔物を倒す
$i$ 番目の刀は、切りつけると $a_i$ 、投げると $b_i$ のダメージを与えられる（ $1 \le a_i \le b_i$ ）
切るのは何度でもできるが、投げると刀は無くなり、それ以上切ることも投げることも出来なくなる
倒すのに必要な最小手数（切る回数＋投げる回数）はいくつか

解法

計算問題だが、考えるべき条件がいくつかある。

攻撃の順番は自由なので、切るだけ切ってから投げるとよい
切る刀は、一番攻撃力（ $a_i$ ）の高い刀だけ使えばよい（ $a_{max}$ とする）
投げる刀は、 $a_{max}$ より攻撃力（ $b_i$ ）が高い刀を投げる
- $b_i$ が $a_{max}$ 以下の刀は、投げずにその分 $a_{max}$ の刀で切った方がよい

とりあえず $b_i$ が高い刀から順に投げて、倒せたらそれまでに投げた本数が答え。

投げるだけでは倒せない場合、切ってダメージを与える。投げた後の残りHPを $R$ とすると、 $ceil(R / a_{max})$ で、切る回数が求められる。

        
              from math import ceil
 
def solve(h, aa, bb):
    max_a = max(aa)
    i = 0
    for b in sorted(bb, reverse=True):
        if b <= max_a:
            break
        i += 1
        h -= b
        if h <= 0:
            return i
    return i + ceil(h / max_a)
 
n, h = map(int, input().split())
aa, bb = [], []
for _ in range(n):
    a, b = map(int, input().split())
    aa.append(a)
    bb.append(b)
 
print(solve(h, aa, bb))