はじめに

この間のAtCoder Beginner Contest(ABC)195のB問題に苦戦したので、復習を兼ねて簡単な解説を書きます。使用言語はpythonを想定しています。 AtCoder Ploblemsによると ABC195ではB問題のほうがC問題より難しかったみたいです。

問題文

みかんがたくさんあります。どのみかんの重さも $A$ グラム以上 $B$ グラム以下であることがわかっています。（みかんの重さは整数とは限りません。）

この中からいくつかのみかんを選んだところ、選んだみかんの重さの合計がちょうど $W$ キログラムになりました。

選んだみかんの個数として考えられる最小値と最大値を求めてください。ただし、このようなことが起こり得ないなら、かわりにそのことを報告してください。

ただし、 $1 \leq A \leq B \leq 1000, 1 \leq W \leq 1000$ である。

解答までの道のり

問題文をよく見る

問題文をみて気になる語句は「みかんの重さは整数とは限りません。」という所。これらを念頭に置くべきなのかもしれません。

実験してみる

B問題の入力例1では参考にならなさそうなので、入力例2つまり、 $(A, B, W) = (120, 150, 2)$ で考えてみます。ここで重要なのが、AtCoderでは出力例の下にある解説は大体こちらを騙して混乱させようとしてくるということです。私は今回、この戦略にまんまと引っかかり、苦戦する羽目になりました。~~みかんの重さを整数にしやがって・・・~~

まず、数が最小のときを考えます。出力例では、最小の数は14なので試しに、1000Wを13や14で割ってみます。

$2000/13 \simeq 153.8 \geq B, 2000/14 \simeq 142.9 \leq B$ である事がわかります。（みかんの重さは少数でも良かったのでした）

よって、 $\dfrac{1000W}{n} \leq B$ が成り立ち、これを変形すると $n \geq \dfrac{1000W}{B}$ となります。

同様に数が最大の時を考えると、 $n \leq \dfrac{1000W}{A}$ が成り立つみたいです。

では、以下のように書けばよいのかというと、そうでもないみたいです。

def LI(): return list(map(int, input().split()))
 
A, B, W = LI()
W *= 1000
 
max_ans = int(W/A)
 
if W%B==0:
    min_ans = int(W/B)
else:
    min_ans = int(W/B) + 1
 
print(min_ans, max_ans)

これでは入力例3 $(A, B, W)=(300,333,1)$ が出力例のUNSATISFIABLEとならず、 $(3, 4)$ となってしまいます。このとき、 $\dfrac{1000W}{A} = 1000/3 = 333.33\cdots \geq B$ となってしまっています。よって、コード中の表現を借りれば、W/max_ans>BとなってしまうときにUNSATISFIABLEとすればよいとわかります。

解答

def LI(): return list(map(int, input().split()))
 
A, B, W = LI()
W *= 1000
 
max_ans = int(W/A)
if W/max_ans>B:
    print('UNSATISFIABLE')
    exit()
 
if W%B==0:
    min_ans = int(W/B)
else:
    min_ans = int(W/B) + 1
 
print(min_ans, max_ans)