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

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

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

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

Python

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

Q&A

解決済

5回答

660閲覧

第3回アルゴリズム実技検定の「C-等比数列」について

退会済みユーザー

退会済みユーザー

総合スコア0

Python 3.x

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

Python

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

0グッド

1クリップ

投稿2020/07/21 10:03

AtCoderの第3回アルゴリズム実技検定の「C-等比数列」の問題についてです。

【問題文】
初項A、公比Rの等比数列の第N項が10^9より大きければlargeを、10^9以下ならその値を整数で出力してください。

【制約】
入力はすべて整数
1 ≦ A,R,N ≦ 10^9

下のコードがタイムアウトになるようなテストケースがいくつかあるようなので、どのような例でそうなるのか教えてほしいです。
正しい解答ではR=1の時とN≧31の時を分岐していますが、intに上限がないPythonでその分岐が必要な理由が分かりません。

Python

1A,R,N = map(int, input().split()) 2ans = A*R**(N-1) 3if ans > 10**9: 4 print('large') 5else: 6 print(ans)

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

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

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

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

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

tiitoi

2020/07/21 10:29

ar^{n - 1} と 10^9 を常用対数を取れば、r^{n- 1} を計算しなくても済むのではないでしょか
guest

回答5

0

ベストアンサー

Nが10^9というべらぼうに大きい数字になっているテストケースでTLEすると思われます。
とても大きいNに対して、そのN-1回分かけて調べればいいかというとそういうわけではありません。
大きいNに対しては、何回かければlargeかどうかがわかるのかというと、2を30回かけると10^9程度なので、2以上の数を31回かけると必ず10^9を超えてしまうことがわかります(答えがlargeになる)
答えがlargeになった時点でさらに掛け算してもlargeなので、largeとわかった時点で切ってしまえばいいわけです。
N-1, もしくは31のどちらか小さい方の回数だけ掛け算すればいいです。

追記)実装例です。

python

1A, R, N = map(int, input().split()) 2ans = A*R**(min(N-1, 31)) 3if ans > 10**9: 4 print('large') 5else: 6 print(ans)

投稿2020/07/21 10:50

編集2020/07/21 11:04
Penpen7

総合スコア698

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

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

0

実際の値を計算する前に大きいかどうかの判定をする

イメージ説明

以下で通りました。

python

1import math 2 3A, R, N = map(int, input().split()) 4 5if math.log10(A) + (N - 1) * math.log10(R) > 9: 6 print("large") 7else: 8 print(A * R ** (N - 1))

正しい解答ではR=1の時とN≧31の時を分岐していますが、intに上限がないPythonでその分岐が必要な理由が分かりません。

int に上限がないことと、計算時間がかかりすぎて AtCorder 側でタイムアウトになるのは別の問題だと思います。

投稿2020/07/21 10:38

編集2020/07/21 10:43
tiitoi

総合スコア21956

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

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

0

計算する桁が増えれば、計算時間は増えます。
あまりに大きな数を計算しようとすれば、制限時間の2秒に間に合わなくなるので、大きな数を計算しないようにしなければならないです。

投稿2020/07/21 10:58

shisha

総合スコア86

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

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

0

intに上限がないPythonでその分岐が必要な理由が分かりません。

AtCoderはご承知の通りPython以外、多数の言語で挑戦することが可能です。ですので言語仕様によってintに上限があるものもあります。そういったものに対応するためのテスト的な問題と思われます。

投稿2020/07/21 10:57

aokikenichi

総合スコア2210

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

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

0

多倍長整数の演算の場合、桁数に比例するレベルの計算量が必要になると考えておいたほうがいいです。
ansの桁数が最大で何桁になるか考えるとタイムアウトは当然でしょう。

投稿2020/07/21 10:40

yudedako67

総合スコア2047

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問