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

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

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

Q&A

解決済

2回答

364閲覧

long long と int (競技プログラミング)

korr

総合スコア23

0グッド

0クリップ

投稿2019/10/21 10:17

編集2019/10/21 10:34

以下のリンクのプログラミング問題について
AtCoder C問題

競技プログラミングで以下のように cnt を定義したのですが、これでは全てのテストコードにおいて WA でした。

C++

1int cnt = 0;

以下に書き換えたら AC できたのですが、調べたらメモリの関係のようでしたがはっきり分かりませんでした。
この問題に関して具体的に教えていただきたいです。

また、forn文のintはllに変えなくていいのはなぜでしょうか?

C++

1ll cnt = 0;

問題の制約
入力は全て整数である。
・ 1≤N≤10^5
・ 1≤A_i≤10^9
・ 1≤B_i≤10^9

C++

1#include<bits/stdc++.h> 2#define forn(i, n) for (int i = 0; i < (int)(n); ++i) 3using namespace std; 4typedef long long ll; 5 6 7int main() { 8 9 int N; 10 cin >> N; 11 vector<int> A(N+1), B(N); 12 forn(i, N + 1) cin >> A[i]; 13 forn(i, N) cin >> B[i]; 14 ll cnt = 0; 15 16 forn(i, N) { 17 if (B[i] <= A[i]) { 18 cnt += B[i]; 19 } else if (B[i] <= A[i] + A[i+1]) { 20 cnt += B[i]; 21 A[i+1] = A[i] + A[i+1] - B[i]; 22 } else { 23 cnt += A[i] + A[i+1]; 24 A[i+1] = 0; 25 } 26 } 27 cout << cnt << endl; 28}

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

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

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

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

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

guest

回答2

0

ベストアンサー

cntには最大10^9を最大10^5回足し算した結果を格納する必要があります。
10^9*10^5=10^14を16進数にすると5af3107a4000となり6Byteすなわち48bit必要です。
intでは収まりません。よって、48bitの値を格納可能であるlong longを使用します。

投稿2019/10/22 08:51

Y.H.

総合スコア7914

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

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

korr

2019/10/22 10:46

分かりやすい説明ありがとうございます
guest

0

表現の範囲の問題でしょ。

競技プログラミングの言語仕様を調べてもらわないとわからないけど、
intが32ビットで
long long が64ビット、とかそんなところじゃなかったかと。

また、forn文のintはllに変えなくていいのはなぜでしょうか?

intの範囲を超えない、ってことがはっきりしてるからじゃないかと

投稿2019/10/21 10:40

編集2019/10/21 11:14
y_waiwai

総合スコア87719

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

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

korr

2019/10/22 07:10

intが32ビットで、long long が64ビットは調べたら出てきたのですが、これが言語仕様と具体的にどのような関係があるのでしょうか。 よろしくお願いいたします。
y_waiwai

2019/10/22 07:18

intやlongのビット長というのは決まってないので、どういうコンパイラを使うかで変わるもんです 数値の表現範囲は、お使いのコンパイラのマニュアルを読もう、というはなしです
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問