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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

2回答

1340閲覧

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

MAMOMIMOMU

総合スコア13

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

1グッド

2クリップ

投稿2020/01/30 04:07

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

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

python

1def digit(x: int) -> int: 2 return len(str(x)) 3def price(A: int, B: int, n: int) -> int: 4 return A*n + B*digit(len(str(n))) 5 6A, B, X = map(int, input().split()) 7pr = 10**9 8pl = 0 9if B > X: 10 print(0) 11elif price(A, B, 10**9) < X: 12 print(10**9) 13else: 14 flag = 0 15 while pr != pl: 16 pc = (pl+pr)//2 17 if X > price(A, B, pc): 18 pl = pc+1 19 elif X < price(A, B, pc): 20 pr = pc-1 21 else: 22 flag = 1 23 if price(A, B, pl-1) < X < price(A, B, pr): 24 ans = pl - 1 25 if price(A, B, pl) < X < price(A, B, pr+1): 26 ans = pl 27 if flag == 1: 28 ans = pc 29 print(ans)

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

退会済みユーザー👍を押しています

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

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なので簡単に答えが求まるのではないかと思います。

投稿2020/01/30 10:07

退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

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などの場合、無限ループに陥ります。

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

投稿2020/01/30 07:09

can110

総合スコア38234

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問