AtCoder Beginner Contest 195 B問題

AtCoder Python

前書き

AtCoder Beginner Contest 195 B問題を解きました。
B問題なのに難解でした。

B問題

  • 難易度：茶
  • 時間：ABCにて解けず→40分(AC)

ABCにて解けなかったB問題を再度挑戦しました。

atcoder.jp

A[g]≤N≤B[g]の重さのみかんが存在します。いくつかのみかんを選んだ時に丁度W[kg]となる最大値と最小値を求める問題です。

思考フローは以下の通りです。

  • 最小値はW*1000/Bの切り捨て、最大値はW*1000/Aの切り上げとなる。→この範囲で１つずつ調査。
  • 最小値の時はBが k 個、最大値の時はAが k ' 個存在している。→kを変えながら調査。
  • W'' = 目標重量 ー( Bがk、Aがk ' の時のみかん総重量 ) → W''が残りのみかん（A≤N≤B）で表現できる数値かを検証。
  • 表現できればその段階で処理を終了する。

このアルゴリズムに至った経緯としては、みかんの個数も自由、選ぶみかんの重さも自由で全探索とかしてたらTLEの危険もありました。
なので数値を固定しながら、残りの重さNがA≤N≤Bの範囲内に収まるアルゴリズムを適用したいと考えていたためでした。

import math
A,B,W=map(int,input().split())
_min, _max=math.ceil(W*1000/B), math.floor(W*1000/A)
_maxFlag, _minFlag = 0, 1001

for i in range(_max,_min-1, -1):
  for j in range(1,i+1):
    if W*1000-(i-j)*A<=B*j and A*j<=W*1000-(i-j)*A: 
      _maxFlag =i
      break
  if _maxFlag!=1001: break

for i in range(_min,_max+1):
  for j in range(1,i+1):
    if W*1000-(i-j)*B<=B*j and A*j<=W*1000-(i-j)*B: 
      _minFlag =i
      break
  if _minFlag!=0: break

if _minFlag==1001 or _maxFlag==0: print('UNSATISFIABLE')
else: print(_minFlag, _maxFlag)

結果

時間はABCで50分考えましたが解けず、今回は30分でテストを重ね何とかACでした。