緊急事態宣言に伴う自粛期間中なので、昨日は家にこもってAtCoder(競技プログラミング)の過去問を練習していました。
昨日は「ABC 162 D - RGB Triplets」を解いていたのですが、なぜかtestcase_17とtestcase_18だけACにならず、長時間悩みました。
結論から言ってしまうとint型同士の演算によるオーバーフローが原因だったのですが、実際のプログラム例を掲載します。
次のC++プログラムにある「R1,R2」「G1,G2」「B1,B2」の各変数は、それぞれ1333を代入しています。
1333は小さな数で、int型の範囲内です。
ただし計算結果は大きな値となるため、long longで受け取ることにしました。
#include <bits/stdc++.h>
using namespace std;
int main() {
int R1 = 1333;
int G1 = 1333;
int B1 = 1333;
long long res1 = R1 * G1 * B1;
cout << res1 << endl; // -1926374259
long long R2 = 1333;
long long G2 = 1333;
long long B2 = 1333;
long long res2 = R2 * G2 * B2;
cout << res2 << endl; // 2368593037
}
見てわかるように、計算結果をlong longで受け取ったとしても、1333をint型にしたパターンでは結果が正しくなりません。
変数に代入するパターンではオーバーフローが起きていたため、次にハードコードで書き直してみました。
#include <bits/stdc++.h>
using namespace std;
int main() {
// ハードコードのint
long long res1 = 1333 * 1333 * 1333;
cout << res1 << endl; // -1926374259
// ハードコードのlong long
long long res2 = 1333LL * 1333LL * 1333LL;
cout << res2 << endl; // 2368593037
}
計算結果は相変わらずですが、私の環境(GCC 9.2.0)では次の警告が発生しました。
これにより、オーバーフローが発生していることがわかります。
$ g++-9 test.cpp
test.cpp: In function 'int main()':
test.cpp:9:34: warning: integer overflow in expression of type 'int' results in '-1926374259' [-Woverflow]
9 | long long res1 = 1333 * 1333 * 1333;
| ~~~~~~~~~~<del>^</del>~~~
発生した警告の内容を見るに、int型同士の演算結果はintになるため、オーバーフローが発生したと推測できます。
左辺で計算結果をlong longで受け取ったとしても、右辺の演算の時点でダメだったようです。
そこで右辺にlong longを組み合わせてみたところ、想定した値が返却されるようになりました。
#include <bits/stdc++.h>
using namespace std;
int main() {
// ハードコードのint
long long res1 = 1333 * 1333 * 1333;
cout << res1 << endl; // -1926374259
// ハードコードのlong long
long long res2 = 1333LL * 1333LL * 1333LL;
cout << res2 << endl; // 2368593037
// intとlong longを組み合わせた例
long long res3 = 1333 * 1333 * 1333LL;
cout << res3 << endl; // 2368593037
}
1333のような小さな値であれば、単にint型へ保存すれば十分だと思っていました。
しかし演算に用いるケースでは、演算結果がとり得る値の範囲や、演算結果の型も考慮したプログラミングが必要であると言えそうです。
C++は競プロのために入門コンテンツを使って速習したくらいの実力なのですが、奥が深くまだまだ学べることがたくさんありそう。
Crieitは誰でも投稿できるサービスです。 是非記事の投稿をお願いします。どんな軽い内容でも投稿できます。
また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!
こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください。
ボードとは?
コメント