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枚でも条件を満たす。どれを答えてもよい。

$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が不可能な組み合わせである

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

• とりあえず $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つずつ調べればよい。

連立方程式から考えると、$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})$ で、切る回数が求められる。