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

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

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

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

Q&A

解決済

1回答

1351閲覧

[AtCoder ABC 129 C Typical Stairs] Pythonのロジックエラーについての質問

sasuke_

総合スコア8

Python

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

0グッド

0クリップ

投稿2020/07/17 01:32

前提・実現したいこと

Pythonで下記の問題を解いておりましたが、どうしてもある入力に対して間違いを出力します
どこのロジックが間違っているか、ご教示いただけますでしょうか
リンク内容

該当のソースコード

python

1#------フィボナッチ数列の処理(上る段数に対する方法の数を数える)------------ 2def fibona(x): 3 import math 4 return (((1/2+math.sqrt(5)/2)**(x+1))-((1/2-math.sqrt(5)/2)**(x+1))) // math.sqrt(5) 5 6def main(): 7#-----inputの処理------------------------- 8 n, m = map(int,input().split()) 9 mlis = [] 10 for _ in range(m): 11 a = int(input()) 12 mlis.append(a) 13 ans = 1 14 mae = -1 15 16 for i in range(m): 17 18#------brokenは壊れている段、maeはその壊れている段の前の壊れている段。隣り合っていたらその時点で終了--------------- 19 broken = mlis[i] 20 if mae == broken - 1: 21 print(0) 22 exit() 23 24#------ひとつ前に壊れていた段の一つ上の段から、壊れている段のひとつ前の段まで登る登り方を求める-------------- 25 nobori = (broken-1) - (mae+1) 26 if nobori == 0: 27 ans *= 1 28 mae = broken 29 else: 30 ans *= fibona(nobori) 31 ans %= (10 ** 9 + 7) 32 mae = broken 33 34#-----すべての壊れている段を考え終えたら、最後の壊れている段の一つ上から、最終段まで登る登り方を数える------- 35 nobori = n - (mae+1) 36 ans *= fibona(nobori) 37 ans %= (10 ** 9 + 7) 38 print(int(ans)) 39 40 41 42if __name__ == "__main__": 43 main() 44

試したこと

サンプルすべてに対して正答を得ているのは確認していますが
本番の入力の一部について内部エラー(1入力分)と、誤答(2入力分)が発生しています
フィボナッチ数列の割り算(ルートで割るため誤差が出る?)や、整数の扱いの問題かとも思いましたが、今のところいずれも解決できていません
恐れ入りますが、ご教示いただけますでしょうか

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

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

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

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

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

guest

回答1

0

ベストアンサー

ほとんど答えは出てますが、フィボナッチ数の計算に浮動小数点を使ってることが原因です。
浮動小数点を使うと上位15桁程度の精度しか出ませんし、この問題だと100000番目のフィボナッチ数が答えになることもあるので浮動小数点でも持て余します。

投稿2020/07/18 12:33

yudedako67

総合スコア2047

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

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

sasuke_

2020/07/19 00:14

ご回答頂きありがとうございます 頂いた方針で、フィボナッチ数列の所を  Decimal / Decimal で処理しようとしましたが、これまでWAだったものの二つまでRE判定になりました(WA2, RE1だったものが、Decimal利用後にRE3判定) 申し訳ありませんが、REと処理される理由はお分かりになるでしょうか・・・?
yudedako67

2020/07/19 00:37

fibona(100000)が正しく計算できることを確かめましたか?
sasuke_

2020/07/20 03:42

ありがとうございました、おっしゃる通り、そもそもそちらで計算できないことを確認しました 確認不足で申し訳ありません。ご教示いただき、ありがとうございました
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.35%

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

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

質問する

関連した質問