0

ソースコードをジャッジにかけた時、一件のみWAが出てしまいます。
このソースコードにおいて、どのような状況下でWAが出るのでしょうか?

問題内容

https://atcoder.jp/contests/abc074/tasks/arc083_a

すぬけ君はビーカーに砂糖水を作ろうとしています。 最初ビーカーは空です。すぬけ君は以下の
4種類の操作をそれぞれ何回でも行うことができます。一度も行わない操作があっても構いません。

・操作 1: ビーカーに水を 100A[g] 入れる。
・操作 2: ビーカーに水を 100B[g] 入れる。
・操作 3: ビーカーに砂糖を C[g] 入れる。
・操作 4: ビーカーに砂糖を D[g] 入れる。

すぬけ君の実験環境下では、水 100[g] あたり砂糖は E[g] 溶けます。

すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。

ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計) が F[g] 以下であり、 ビーカーの中に砂糖を溶け残らせてはいけないとき、
すぬけ君が作る砂糖水の質量と、それに溶けている砂糖の質量を求めてください。 答えが複数ある場合はどれを答えても構いません。

水 a[g] と砂糖 b [g] を混ぜた砂糖水の濃度は 100ba+b [%]です。 また、この問題では、砂糖が全く溶けていない水も濃度0 [%] の砂糖水と考えることにします。

回答方針

大まかには以下の流れでソースコードを記述しました。

  1. 水の取り得るパターンを列挙
  2. 砂糖の取り得るパターンを列挙
  3. 水と砂糖の組み合わせを全検証し、最大濃度の組み合わせを探す

ソースコード

def concentration(water, suger):
  return 100 * suger / (water + suger)

WATER_A, WATER_B, SUGER_C, SUGER_D, MELT_PER_100, LIMIT = map(int, input().split())

WATER_A *= 100
WATER_B *= 100
# 砂糖の溶解率の上限
MELT_PERCENT_LIMIT = concentration(100, MELT_PER_100)

wa = wb = sc = sd = 0

water_set = set()
while wa * WATER_A <= LIMIT:
  while wb * WATER_B <= LIMIT:
    water = wa * WATER_A + wb * WATER_B
    if water <= LIMIT:
      water_set.add(water)
    wb += 1
  wb = 0
  wa += 1

suger_set = set()
while sc * SUGER_C <= LIMIT:
  while sd * SUGER_D <= LIMIT:
    suger = sc * SUGER_C + sd * SUGER_D
    if suger <= LIMIT:
      suger_set.add(suger)
    sd += 1
  sd = 0
  sc += 1

ans_suger_water = 0
ans_suger = 0
# 最大溶解率を保持するための変数
max_concentration = 0

for water in water_set:
  for suger in suger_set:
    # 砂糖水の量が0より大きく制限量以下以外の場合は次のループへ
    if not (0 < water + suger <= LIMIT):
      continue
    # 砂糖濃度計算
    suger_precent = concentration(water, suger)
    # 砂糖濃度が最高を更新かつ限界濃度を超えていなければ答えを更新
    if max_concentration < suger_precent <= MELT_PERCENT_LIMIT:
      max_concentration = suger_precent
      ans_suger_water = water + suger
      ans_suger = suger

print(ans_suger_water, ans_suger)

1 件の回答 1

1

おそらく出題中のこの設定がキーになっているものと思われます。

この問題では、砂糖が全く溶けていない水も濃度0 [%] の砂糖水と考えることにします。

つまり、条件を満たすようにすると濃度0%の砂糖水しかできない場合、それを結果として出力しないといけません。

次のような入力で試してみてください。

1 2 10 20 1 200

あなたのコードからはこんな結果が出ます。

0 0

濃度0%がOKなら、これもOKのように思われるかもしれませんが、0/0の値は定義できませんし、砂糖水自体が0gというのは出題の条件を満たしているとは言えないでしょう。

出題から読み取れる正しい結果は、

100 0

または、

200 0

と考えられます。


私の目検だけですが、回答方針の1., 2.に相当する部分の列挙には問題がないように思われるので、3.の「全検証」の部分の条件が微妙に間違っていて、初期値の0 0が出力されているものと思われます。

そのつもりで条件判定をしている部分をよく見直すと、2つ目のif条件が気になります。

    if max_concentration < suger_precent <= MELT_PERCENT_LIMIT:

出題の条件により、砂糖濃度0%は有効な解なのに、max_concentrationの初期値が0であるため、suger_precentが0と算出された場合、解を表す変数は更新されません。

一番簡単には、max_concentrationの初期値を変更してやるといいでしょう。

max_concentration = -1

これで、上記の入力例1 2 10 20 1 200に対する出力例は、

100 0

となります。

私がチェックした限り他に穴は見つけられなかったので、一度お試しいただければと思います。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。