質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.59%

二分探索も用いた問題(Pyhton)

受付中

回答 2

投稿

  • 評価
  • クリップ 2
  • VIEW 418

MAMOMIMOMU

score 10

Atcoderの第146回Beginners contestのC問題を解いてみたのですが、よくわかりませんでした。
問題はこちらです。

私のコードがこちらになります。

def digit(x: int) -> int:
    return len(str(x))
def price(A: int, B: int, n: int) -> int:
    return A*n + B*digit(len(str(n)))

A, B, X = map(int, input().split())
pr = 10**9
pl = 0
if B > X:
    print(0)
elif price(A, B, 10**9) < X:
    print(10**9)
else:
    flag = 0
    while pr != pl:
        pc = (pl+pr)//2
        if X > price(A, B, pc):
            pl = pc+1
        elif X < price(A, B, pc):
            pr = pc-1
        else:
            flag = 1
    if price(A, B, pl-1) < X < price(A, B, pr):
        ans = pl - 1
    if price(A, B, pl) < X < price(A, B, pr+1):
        ans = pl
    if flag == 1:
        ans = pc
    print(ans)

いくつかのテストサンプルでは通るのですが、誤答の出力もあるみたいです。こう改良した方がよい、ここが間違っている等のご指摘お願い致します。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

0

気づいた点のみ。

まずはreturn A*n + B*digit(len(str(n)))は問題どおりの式を表しているでしょうか?
また、これを正しく修正したとしても

  • 1 2 3の場合、UnboundLocalError: local variable 'ans' referenced before assignmentが発生します。if B > Xという判定は妥当でしょうか?
  • 1 2 4などの場合、無限ループに陥ります。

全体的に処理を見直してみたほうがよいかもしれません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

スマホからなので動作確認とかは出来ていませんが

digit(len(str(n)))
まずここがおかしくてdigit(n)ですね。

while文内のif文がelseの時にplもprも更新されず永久ループに陥りそうです。
ここらはケアレスミスですね。

そして最後3つのif文ですが
price(A, B, pl-1) < X < price(A, B, pr):
これは恐らくループ内最後の判定が
if X > price(A, B, pc):
である場合を想定しているのだと思いますが、X < price(A, B, pr)である保証がなく、もう一方も同様なのでいずれの条件にも引っかからない場合があります(pr+1は保証されてる)

で、別の考え方ですが
N=10^k+n (0≦n<10^k)
とすると
A(10^k+n)+B(k+1)≦X
が条件なので
An≦X-A*10^k-B(k+1)
となるkとnの組のうちNが最大となるものを探せばよく
kは最大でも17なので簡単に答えが求まるのではないかと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.59%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る