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

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

新規登録して質問してみよう
ただいま回答率
85.43%
C++

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

Q&A

解決済

1回答

344閲覧

c++ 間違いを教えていただきたいです。

miwawa.1

総合スコア5

C++

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

0グッド

1クリップ

投稿2024/06/13 15:57

実現したいこと

コード中の間違いを教えていただきたいです

発生している問題・分からないこと

Atcoder ABC289 D問題において、dp配列をbool型でもった際はACするのですがint型でもつとうまくいかないということがありました。なぜ、int型だとうまくいかないのか教えていただきたいです。
下記にコードを載せておきます。最初のがbool型です。

bool型

#include <bits/stdc++.h>
#include <cmath>
using ll=long long;
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;

int main(){
ll n,q,y=0,i,z=0,x=0,d=0,k,L,nk,sum=0,t;
int ans=2e9+10,sum2=0,rs=-1e9,cs=0,l=0,h=0,w=0,r=0,X;
ll tmp2=0,flag=0,a=0,b=0,c=0,j=0,m=0,p;
cin>>n;
vector<int>ar;
vector<bool>br(200010,false);
vector<int>dp(300010,0);
rep(i,0,n){
cin>>x;
ar.push_back(x);
}
cin>>m;
rep(i,0,m){
cin>>x;
br[x]=true;
}
cin>>X;
dp[0]=true;
rep(i,0,100010){
if(br[i])continue;
rep(j,0,ar.size()){
if(dp[i])dp[i+ar[j]]=true;
}
}
if(dp[X])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
///////////////////////////////////////////
次がint型です。

#include <bits/stdc++.h>
#include <cmath>
using ll=long long;
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;

int main(){
ll n,q,y=0,i,z=0,x=0,d=0,k,L,nk,sum=0,t;
int ans=2e9+10,sum2=0,rs=-1e9,cs=0,l=0,h=0,w=0,r=0,X;
ll tmp2=0,flag=0,a=0,b=0,c=0,j=0,m=0,p;
cin>>n;
vector<int>ar;
vector<int>br(200010,0);
vector<int>dp(300010,0);
rep(i,0,n){
cin>>x;
ar.push_back(x);
}
cin>>m;
rep(i,0,m){
cin>>x;
br[x]++;
}
cin>>X;
dp[0]=1;
rep(i,0,100010){
if(br[i]!=0)continue;
rep(j,0,ar.size()){
dp[i+ar[j]]+=dp[i];
}
}
if(dp[X]!=0)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}

エラーメッセージ

error

1エラーは出てないです

該当のソースコード

c++

1//bool型 2 3#include <bits/stdc++.h> 4#include <cmath> 5using ll=long long; 6#define rep(i,a,b) for(int i=a;i<b;i++) 7using namespace std; 8 9int main(){ 10 ll n,q,y=0,i,z=0,x=0,d=0,k,L,nk,sum=0,t; 11 int ans=2e9+10,sum2=0,rs=-1e9,cs=0,l=0,h=0,w=0,r=0,X; 12 ll tmp2=0,flag=0,a=0,b=0,c=0,j=0,m=0,p; 13 cin>>n; 14 vector<int>ar; 15 vector<bool>br(200010,false); 16 vector<int>dp(300010,0); 17 rep(i,0,n){ 18 cin>>x; 19 ar.push_back(x); 20 } 21 cin>>m; 22 rep(i,0,m){ 23 cin>>x; 24 br[x]=true; 25 } 26 cin>>X; 27 dp[0]=true; 28 rep(i,0,100010){ 29 if(br[i])continue; 30 rep(j,0,ar.size()){ 31 if(dp[i])dp[i+ar[j]]=true; 32 } 33 } 34 if(dp[X])cout<<"Yes"<<endl; 35 else cout<<"No"<<endl; 36 } 37///////////////////////////////////////////// 38//int型 39 40#include <bits/stdc++.h> 41#include <cmath> 42using ll=long long; 43#define rep(i,a,b) for(int i=a;i<b;i++) 44using namespace std; 45 46int main(){ 47 ll n,q,y=0,i,z=0,x=0,d=0,k,L,nk,sum=0,t; 48 int ans=2e9+10,sum2=0,rs=-1e9,cs=0,l=0,h=0,w=0,r=0,X; 49 ll tmp2=0,flag=0,a=0,b=0,c=0,j=0,m=0,p; 50 cin>>n; 51 vector<int>ar; 52 vector<int>br(200010,0); 53 vector<int>dp(300010,0); 54 rep(i,0,n){ 55 cin>>x; 56 ar.push_back(x); 57 } 58 cin>>m; 59 rep(i,0,m){ 60 cin>>x; 61 br[x]++; 62 } 63 cin>>X; 64 dp[0]=1; 65 rep(i,0,100010){ 66 if(br[i]!=0)continue; 67 rep(j,0,ar.size()){ 68 dp[i+ar[j]]+=dp[i]; 69 } 70 } 71 if(dp[X]!=0)cout<<"Yes"<<endl; 72 else cout<<"No"<<endl; 73 }

試したこと・調べたこと

  • teratailやGoogle等で検索した
  • ソースコードを自分なりに変更した
  • 知人に聞いた
  • その他
上記の詳細・結果

Atcoder ABC289 D問題において、dp配列をbool型でもった際はACするのですがint型でもつとうまくいかないということがありました。なぜ、int型だとうまくいかないのか教えていただきたいです。

補足

特になし

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

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

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

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

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

guest

回答1

0

ベストアンサー

ご提示のint型のコードでは、解が何通りあるかを計算していますが、パターン数が多すぎてintの範囲を超えてしまい、オーバーフローが発生しています。その結果、値がちょうど0に等しくなってしまい、if(dp[X]!=0)でもテストケースが通らない場合が出てきます。

例えば、以下の小さな入力に対してさえ、解は2,971,215,073通りになってしまいます。intの最大値は2,147,483,647なので、オーバーフローが発生します。

2 1 2 1 2 49

投稿2024/06/13 21:21

編集2024/06/13 21:40
actorbug

総合スコア2274

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

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

miwawa.1

2024/06/14 00:11

回答ありがとうございます。 試したところ問題が解決しました! ベストアンサーに選ばせていただきました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.43%

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

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

質問する

関連した質問