21 最小と最大 Dif:483 ABC195 B：「AtCoder 凡人が『緑』になるための精選50問詳細解説」サンプル

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/a86795c3851db8a897b9
次：https://qiita.com/sano192/items/780e1c4751b60cb0c8ed

【目標】
・条件を満たす中での最小、または最大を求める問題を解けるようになる

【概要】
いつもはなんなくB問題を解けるという人でもこの問題に苦戦した人は多かったと思う。この手の問題の解法を自分で思いつくのは難しい。しかし「条件を満たす中での最小、または最大を求める問題」というのは解き方が決まっているのでそれを知っていれば簡単。この問題でやり方を身に着けよう。

【方針】
条件を満たす中での最小、または最大を求める問題では、答えの候補となる数について条件を満たすか順に確かめる、という方法を使う。

具体的に言うとこの問題では1個、2個、...が問題の条件を満たすか？ということを順に計算する。

X個が条件を満たすか？をどう判定するか。
1個あたりの重さはAグラム~Bグラム
ゆえに
X個の当たりの重さはAXグラム~BXグラム
ということになる。
よってXが以下の条件を満たせば良い。
AX<=1000W<=BX
(Wキログラムをグラムに直すために1000倍している)

次に考えるのはXの探索範囲、つまり条件を満たしうる最大の個数。
条件を満たしうる最大の個数はみかん1個あたりの重さが最小かつ重さの合計が最大、つまり
B=1かつW=1000
この場合条件を満たす最大の個数は10^6個。
よってX=1,２,...,10^6まで順に条件を満たすか計算して確認すればよい。

【実装】
入力を受け取る。

A,B,W=map(int, input().split())

Wはキログラムだが1000倍してグラムに直す。

W_g=W*1000

答えの最小値、最大値を格納する変数を作っておく。
最小値の初期値はバカでかい数(=10^15)
最大値の初期値はとてつもなく小さい数(=-10^15)
にしておく。
この問題に限らず最小値、最大値を求める問題の初期値はいつもそのように決めると覚えておこう。

min_ans=10**15
max_ans=-10**15

X=1、2、...が条件を満たすか順に確かめる。【方針】で説明したとおり、Xは最大10^6で十分だがてきとうにそれより少し大きな数として10^6+9まで探索している。

for X in range(1,10**6+10):
    if A*X<=W_g<=B*X:
        min_ans=min(min_ans,X)
        max_ans=max(max_ans,X)

後は答えの出力。
もし最小値=min_ansが一度も更新されていなければ条件を満たすXは存在しなかったということなので"UNSATISFIABLE"を出力する。

if min_ans==10**15:
    print("UNSATISFIABLE")

else:
    print(min_ans,max_ans)

この問題のようにB問題がやたら難しいということはたまに起きる。コンテスト中にB問題が解けないと焦るだろうが、さっさと諦めてC問題に移ろう。解ける問題を全て終わらせてから解けない問題を考えたほうがよい。
実際このコンテストはB問題よりC問題の方が簡単だったため、早めにB問題を捨ててC問題に取り掛かった人のほうが順位が高くなった。

【コード全文】

A,B,W=map(int, input().split())

W_g=W*1000

min_ans=10**15
max_ans=-10**15

for X in range(1,10**6+10):
    if A*X<=W_g<=B*X:
        min_ans=min(min_ans,X)
        max_ans=max(max_ans,X)

if min_ans==10**15:
    print("UNSATISFIABLE")

else:
    print(min_ans,max_ans)

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/a86795c3851db8a897b9
次：https://qiita.com/sano192/items/780e1c4751b60cb0c8ed