問題
要約
-
高橋くんは整数屋さんで整数を1つ買おうとしている。
-
整数屋さんでは、1以上10^9以下の整数が売られている。
-
整数Nを買うためには、A × N + B × d(N) 円が必要。
ここで、d(N)はNの十進表記での桁数。 -
高橋くんの所持金はX円。
-
高橋くんが買うことのできる最も大きい整数を求める。
-
買うことのできる整数が1つもない場合は0を出力する。
変数情報：
- N: 購入する整数（1 ≤ N ≤ 10^9）
- A: 整数の価格を計算するための係数
- B: 整数の桁数に関連する価格係数
- X: 高橋くんの所持金
- d(N): Nの十進表記での桁数
既存投稿一覧ページへのリンク
アプローチ
二分探索を用いて、高橋くんが購入可能な最大の整数を見つける。
解法手順
-
入力値A, B, Xを受け取る。
-
整数Nの価格を計算する関数functionを定義する。この関数は、A × N + B × d(N)を計算して返す。
-
最小の整数1でも購入できない場合（X < function(1)）、0を出力して終了する。
-
二分探索の初期範囲を設定する。左端（left）を1、右端（right）を10^20とする。
-
二分探索を行う：
a. 中間値（middle）を計算する。
b. function(middle)がX以下なら、leftをmiddleに更新する。
c. そうでなければ、rightをmiddleに更新する。
d. left + 1 < rightの間、この過程を繰り返す。 -
最終的なleftが10^9を超える場合、leftを10^9に設定する（問題の制約による）。
-
得られたleftを出力する。これが購入可能な最大の整数となる。
ACコード
def io_func():
# 入力値A, B, Xを受け取る
return map(int, input().split())
def function(n, A, B):
# 整数Nの価格を計算する関数
N_str = str(n) # 整数nを文字列に変換
d = len(N_str) # 桁数を取得
return A * n + B * d # 価格を計算して返す
def solve(A, B, X):
# 最小の整数1でも購入できない場合、0を出力して終了
if X < function(1, A, B):
return 0
# 二分探索の初期範囲を設定
left = 1
right = 10**20
# 二分探索を行う
while left + 1 < right:
middle = (left + right) // 2 # 中間値を計算
if function(middle, A, B) <= X:
left = middle # leftをmiddleに更新
else:
right = middle # rightをmiddleに更新
# 最終的なleftが10^9を超える場合、10^9に設定
if 10**9 < left:
left = 10**9
return left # 購入可能な最大の整数を返す
if __name__=="__main__":
# メイン処理
A, B, X = io_func() # 入力を受け取る
result = solve(A, B, X) # 解を求める
print(result) # 結果を出力
###
# A: 整数の値段の係数
# B: 整数の桁数の係数
# X: 高橋くんの所持金
# left: 二分探索の左端
# right: 二分探索の右端
# middle: 二分探索の中間値
# result: 購入可能な最大の整数
# 1. io_func関数: 標準入力から値を受け取る
# 2. function関数: 整数Nの価格を計算する
# 3. solve関数: 二分探索を用いて購入可能な最大の整数を求める
# - 最小の整数1でも購入できない場合の処理
# - 二分探索の初期範囲の設定
# - 二分探索のループ処理
# - 結果が10^9を超える場合の調整
# 4. メイン処理: 入力を受け取り、solve関数を呼び出し、結果を出力する
思考過程
問題の性質上、購入可能な整数には単調性があり（より小さい整数が購入可能なら、それ以下の整数も購入可能）、これが二分探索の適用を可能にしている。
計算量の概算
二分探索の計算量はO(log N)。
その他周辺知識
価格計算
return A * n + B * d
条件分岐
if X < function(1, A, B):
return 0
この部分は、最小の整数1でも購入できない場合を確認する。
function(1, A, B)で1の価格を計算し、それが所持金Xより大きければ0を返す。
二分探索の初期設定
left = 1
right = 10**20
二分探索の初期範囲を設定する。
leftは1から、rightは非常に大きな数（10の20乗）
二分探索のループ
while left + 1 < right:
middle = (left + right) // 2
left + 1 < rightの間ループを続ける。
middleはleftとrightの中間値。
二分探索の条件分岐
if function(middle, A, B) <= X:
left = middle
else:
right = middle
middleの価格が所持金以下ならleftを更新し、そうでなければrightを更新する。