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

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

ただいまの
回答率

90.84%

  • C++

    3128questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

サイコロをn回投げて出た目の総積がDの倍数となる確率は? C++

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 154

cbeginner

score 1

 前提・実現したいこと

atcoderというプログラミングコンテストをオンラインで開催しているサイトに載っていたこの質問のタイトルにある問題について、自分のソースコードの間違いを指摘して頂けるとありがたいです。標準入力で整数値n(1<=n<=100),D(1<=D<=1e18)が与えられ、絶対誤差1e-6以下で正しい値を出力できれば正解となります。
↓こちらのリンクから問題の詳細が確認できます。
https://beta.atcoder.jp/contests/tdpc/tasks/tdpc_dice

 発生している問題・エラーメッセージ

1つのテストケースにのみ正解できていません。(テストケースの中身は全て非公開になっています。)

 該当のソースコード

#include <bits/stdc++.h> 
using namespace std;

#define db double
#define rep0(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repU(i,bottom,ceiling) for(int (i)=(bottom);(i)<=(ceiling);(i)++)
#define repD(i,ceiling,bottom) for(int (i)=(ceiling);(i)>=(bottom);(i)--)
#define V vector
#define vi vector<int>
#define pub(v,el) v.push_back(el)
#define pob(v) v.pop_back
#define ci(a) cin>>a
#define lco(a) cout<<a<<endl
#define co(a) cout<<a
#define vco(v) rep0(i,v.size()){ co(v[i]<<' '); } co('\n')
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
#define fir first
#define sec second

typedef long long ll;

const int dir[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
const int Inf=2e9+1e8;

template <typename T,typename U>                                                   
pair<T,U> operator+(const pair<T,U> & l,const pair<T,U> & r) {   
    return {l.fir+r.fir,l.sec+r.sec};                                    
} 

template <typename T,typename U> 
pair<T,U> operator-(const pair<T,U> & l,const pair<T,U> & r) {   
    return {l.fir-r.fir,l.sec-r.sec};                                    
} 

int order(ll n,int p){
    if((ll)n%p) return 0;
    return 1+order(n/(ll)p,p);
}

int main(){
    int n,p[3];
    ll d;
    ci(n>>d);
    p[0]=order(d,2);
    p[1]=order(d,3);
    p[2]=order(d,5);
    if(d/(1<<p[0])/pow(3,p[1])/pow(5,p[2])>1){
        lco('0');
        return 0;
    }
    V<V<V<V<db>>>> dp=V<V<V<V<db>>>>(n+1, V<V<V<db>>>(p[0]+1,V<V<db>>(p[1]+1,V<db>(1+p[2],0))));
    dp[0][0][0][0]=1;
    repU(cnt,0,n){
        repU(a,0,p[0]){
            repU(b,0,p[1]){
                repU(c,0,p[2]){
                    if(!cnt){ if(a||b||c){ dp[cnt][a][b][c]=0; } continue; }
                    dp[cnt][a][b][c]= (dp[cnt-1][a][b][c]+dp[cnt-1][max(0,a-1)][b][c]+dp[cnt-1][a][max(0,b-1)][c]+dp[cnt-1][a][b][max(0,c-1)]+dp[cnt-1][max(0,a-2)][b][c]+dp[cnt-1][max(a-1,0)][max(0,b-1)][c])/6;
                }
            }
        }    
    }
    printf("%.10f\n",dp[n][p[0]][p[1]][p[2]]);
    return 0;
}

 試したこと

コーナーケースを念入りに確認したつもりです。

 補足情報(FW/ツールのバージョンなど)

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • okrt

    2018/05/23 23:24

    問題のアドレスは消さないほうが親切ですね

    キャンセル

  • cbeginner

    2018/05/24 07:12

    iPadではリンクとして機能しておらずコピーも出来なかったため消してしまいました。貼り直しておきます。

    キャンセル

  • mkgrei

    2018/05/24 07:28

    自前のマクロが激しすぎるせいでバグを誘発しやすい状況にあるように見えるのですが、あえて別言語のようにして回答者の方に見てもらいたいのですか?普通に書かれた方が回答を得やすいかと思われます。一応。

    キャンセル

  • cbeginner

    2018/05/24 07:38

    意見ありがとうございます。僕はコーディングスキルが低く、今回のコードのように4次元vectorなどを用いる場合も少なくないため、その宣言等において自分に見やすくするというのが主な目的です。mkgreiさんの意見も踏まえ今後の投稿ではより読みやすいコードを付すことを心がけたいと思います。

    キャンセル

回答 2

checkベストアンサー

0

部分的に読んだだけですが、

if(d/(1<<p[0])/pow(3,p[1])/pow(5,p[2])>1)


は怪しいです。
例えば
99 1125899906842624
が入力された場合、Dは2の50乗なので99回の積がDの倍数になるパターンは多数存在するはずですが、このコードでは多くの環境で0になると思います。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/05/24 07:31

    ありがとうございます。確かに(99,2^50)という入力に対しては0が出力されました。そこでorderの取り方を少し変更して上手く行きました。(https://beta.atcoder.jp/contests/tdpc/submissions/2552826)
    また、単に1,3,5をlong longへキャストしてから使用するように変更してもやはり成功しました。(https://beta.atcoder.jp/contests/tdpc/submissions/2552830)
    やはり元のコードの欠陥というのは、定数1,3,5がintとしてメモリ確保されていたために左シフト後の値、あるいはpowに入れた結果がオーバーフローしうる点だった、と結論づけてよいのでしょうか?

    キャンセル

  • 2018/05/24 21:47

    そうですね。
    シフトやpowの結果が32bitで扱える範囲を超える可能性があったのにintで演算してたから、intが32bitの環境では不正解になっていた
    ということで良いと思います。

    キャンセル

0

サンプルインプット2 6の結果がサンプルアウトプット0.416666667と異なります
すいません。絶対誤差による判定でしたね

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/05/23 22:32

    そのサンプルに対してはコードテストでは絶対誤差1e-6の範囲で出力できています。

    キャンセル

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

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

関連した質問

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

  • C++

    3128questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。