くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 146 C - Buy an Integer

Python3で解く AtCoder Beginner Contest 146 C - Buy an Integer

AtCoder 競プロ ABC-C 二分探索

単純に計算すると計算量多すぎるので、桁の条件を詰めつつ最大値を求める方法と二分探索がある。

目次

概要

問題

  1. {\displaystyle 1 \leqq n \leqq} 10^9の整数{\displaystyle n}を買いたい。
  2. 買うには、{\displaystyle a \times n + b \times d}円必要。（{\displaystyle d}は{\displaystyle n}の桁数）
  3. {\displaystyle x}円持ってるけど買える最大の{\displaystyle n}は？

解くときに考えた内容

全探索すると{\displaystyle 10^9}なので計算量を減らす必要がある。そこで以下の方法が考えられる。多くの人が二分探索でやっているので、主に違う方法やったものを扱う。

  • 条件を満たす最大の桁における{\displaystyle n}を計算

    • {\displaystyle n}が最大{\displaystyle 10^9}の時、条件{\displaystyle a \times n + b \times d \leqq x}（{\displaystyle d}は{\displaystyle n}の桁数）を満たしたら、{\displaystyle n = 10^9}
    • {\displaystyle a + b > x}だったら、{\displaystyle n = 0}
    • そうじゃなかったら、{\displaystyle n = 1, 10, 100 ... 10^9}の順に「桁ごとに」{\displaystyle a \times n + b \times d \leqq x}を満たす最大の{\displaystyle n}を計算する
    • 上記で最終的に最大の桁において、{\displaystyle x - b \times d}の{\displaystyle a}で割った時の商が求めたい最大の{\displaystyle n}となる。

  • 二分探索
    単純に条件{\displaystyle a \times n + b \times d} {\displaystyle \leqq x}を満たすような {\displaystyle n}を見つける。（{\displaystyle d}は{\displaystyle n}の桁数）

コード

条件を満たす最大の桁における{\displaystyle n}を計算
a, b, x = map(int, input().split())
maxv = 0
if a * 10 ** 9 + b * 10 <= x:   
    print(10**9)
elif a + b > x:
    print(0)
else:
    n = 10**0
    while a * n + b * len(str(n)) <= x:
        maxv = (x-b*len(str(n))) // a
        if len(str(maxv)) != len(str(n)):
            maxv = n * 10 -1
            # 桁ごとの最大のn
            # print(maxv)
        n *= 10
    print(maxv)
二分探索
from bisect import bisect_right

a, b, x = map(int, input().split())
# 二分探索
l = 0
r = 10 ** 9 + 1
while r - l > 1:
    n = (r+l) // 2
    if a * n + b * len(str(m)) <= x:
        l = n
    else:
        r = n
print(l)