パナソニックプログラミングコンテスト(ABC195 A - Health M Death / B - Many Oranges)【Python解答例】

AtCoder Beginner Contest195のA - Health M DeathとB - Many OrangesについてPythonの解答例を記事にしました。
Panasonic Programming Contest (AtCoder Beginner Contest 195) - AtCoder

AtCoder Beginner Contest 195 A - Health M Death

A - Health M Death

問題文

魔法使いの高橋君がモンスターと戦っています。
高橋君が魔法を使うと、体力が M の倍数であるモンスターを倒すことができます。体力が M の倍数でないモンスターに対しては何の効果もありません。
高橋君の魔法によって、体力が H のモンスターを倒すことができるでしょうか？

制約

・1≤M≤1000
・1≤H≤1000
・M 及び H は整数

解答例

m, h = map(int,input().split())

if h % m == 0:
    print("Yes")
else:
    print("No")

解説

HがMの整数倍か答える問題です。

割り算して余りを確認すればいいので、余りを求める％演算子を使います。
余りが0ならYes、0でなかったらNoを出力すればACでした。

AtCoder Beginner Contest195 B - Many Oranges

B - Many Oranges

問題文

みかんがたくさんあります。どのみかんの重さも A グラム以上 B グラム以下であることがわかっています。（みかんの重さは整数とは限りません。）
この中からいくつかのみかんを選んだところ、選んだみかんの重さの合計がちょうど W キログラムになりました。
選んだみかんの個数として考えられる最小値と最大値を求めてください。ただし、このようなことが起こり得ないなら、かわりにそのことを報告してください。

制約

・1≤A≤B≤1000
・1≤W≤1000
・入力は全て整数

解答例

a, b, w = map(int,input().split())

weight = w * 1000 # 単位合わせ

flag = True # 組み合わせが起こり得るか判別フラグ

# 最大値を求める
tmp = weight // a # 余り切り下げ
if tmp * a <= weight and tmp * b >= weight:
    max_num = weight // a
else:
    flag = False

# 最小値を求める
tmp = -(-weight // b) # 余り切り上げ
if tmp * a <= weight and tmp * b >= weight:
    min_num = -(-weight // b)
else:
    flag = False

if flag:
    print(min_num, max_num)
else:
    print("UNSATISFIABLE")

解説

Aグラム以上、Bグラム以下のみかんをいくつでも選べるとき、重さの合計をWキログラムにできるかどうか、できるならみかんの個数の最小値と最大値を答える問題です。
解説では全探索していましたが、コンテスト中に思いついた方法を記載します。

標準入力のWはキログラム単位でA,Bグラムと単位が違うので単位合わせを行います。

みかんの個数の最大値は重さを余り切り下げでAで割った値が候補(tmp)です。
この値×Aと同じ値×Bの間にW[g]があれば、Wを作り出せることが可能で、最小値となります。
tmp+1個では必ずWを超えてしまうので、候補となる値はtmp以外にないと思います。

みかんの個数の最小値はBで割って余りを切り上げた値(tmp)を候補とします。
最小値と同じようにA×tmpとB×tmpの間にWがあれば、最大値となります。

もし最大値と最小値が存在していたら値を出力し、なければUNSATISFIABLEを出力すればACです。

B問題は余りの切り上げ、切り下げで頭を悩ませましたが解けてよかったです。
全探索で解けることはコンテスト中は全然気が付きませんでした (^_^;)
今回もD問題まで復習していきたいです。

ABC195の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com