人はなぜ、long long を使うのか？ (競技プログラミング)

ここで紹介するテクニックは競技プログラミング専用です。業務で使うのを控えましょう。

競技プログラミングを始めたての人がAtCoderの300点問題を解いてて「解法にミスはないですし、手元のテストケースは全部あってるはずなのにACしません！！」という言葉を使う光景をよく目にします。

当然、ただ単純にミスの場合も多いのですが、200点問題だと遭遇しないようなケースにハマってしまい苦戦していることも少なくありません。

その200点問題では遭遇しないケースとはなんなのかというと、それは 整数のオーバーフロー です。

整数のオーバーフローとは？

C++の整数型であるint型には上限値と下限値が設定されています。
その上限値は2,147,483,647、下限値は-2,147,483,648です(ざっと21億くらい)。
仮にこの範囲をオーバーしてしまうとどうなるのでしょうか？

結論から言うと環境に依存したランダムな値が変数に格納されます。
実際の例が以下のような形ですね。

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

int main() {
  int a = 9223372036854775807;
  cout << a << endl;
}

$ ./test
-1

このように巨大な整数を表示したいのに、全く別の -1 という整数が表示されています。
さて、このような場合ですが、どのようにすれば解決することができるのでしょうか？

long long int

C++にはこの解決策としてさらに下限値、上限値が大きい変数が用意されています。
その変数というのが long long 型です(正式名は long long int)。

この変数の下限値と上限値は以下のようになっています。
下限値: -9,223,372,036,854,775,808
上限値: 9,223,372,036,854,775,807
(ざっと 922景 くらい)

これを使うことによって、先ほどのような巨大な整数も問題なく扱うことができます。

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

int main() {
  int a = 9223372036854775807;
  cout << "int: " << a << endl;
  long long lla = 9223372036854775807;
  cout << "long long: " << lla << endl;
}

$ ./test
int: -1
long long: 9223372036854775807

どういう時に使うのか？

当然ですが上記のような巨大な数値を扱うタイプの問題です。
列挙してみると以下のような感じです。

• $10^9$を超える数値を扱う可能性のある問題
• $10^5$のような比較的大きな数値同士の掛け算を行う可能性のある問題
• $10^5$のような比較的大きな数値を何度も1つの変数に格納していく可能性のある問題

以上です。ここで可能性と書いたのは、テストケースだとこういった巨大な入力例を載せている問題はあまり多くないからです。なので、問題文と制約を注意深く確認して long long を使う必要があるのかを判別していく必要があります。

えっと...全部 long long 型を使うのはダメなんですか？

結論から言うとOKです。
競技プログラミングで出題される問題で int型だけだと long long型　だと ACできないという問題はほとんどない(はず)です。なので、以下のような形で int型 を 全て long long型に置き換えてしまっている例も時々見ます。(僕はしてないです)

#include<bits/stdc++.h>
using namespace std;
typedef long long int; // これを表記するとintと記載するとlong longと認識されるようになる

int main() {
  int a = 9223372036854775807; // 正常に格納可能。
  cout << a << endl;
}

メモリのお話

ここからは競技プログラミングの話ではないので、「使い方だけ知りたいよ！」という方はこのままブラウザバックしていただいてOKです。

そもそもですがなぜint型の上限値は2,147,483,647なのでしょうか？
その秘密はコンピュータの整数の管理方法にあります。

コンピュータでは文字列、画像、音声データ...などの様々な情報を 1 と 0 の数字だけで管理しています。当然、整数も 1 と 0 だけで管理されています。

そこで使用されるのが 2進数 です。2進数の具体的な説明はここでは省略しますが、1を超えると桁上がりする数字の数え方です。

そして、肝心のint型ですが、これには32bitのメモリが割り当てられています。16bitとは 1 と 0 のスイッチが32個もあり、組み合わせを帰ることにより数字を表現しているのです。そして、それによって表現できる数字の数が $2^{32}$ 個、すなわち 4,294,967,296 個です。

ただ、int方にはご存知の通り、正負の概念があるので　上限値、下限値がその半分である 2,147,483,648 と -2,147,483,648 になります。また、上限値は 0 もカウントする必要があるため、そこから 1 を引いた 2,147,483,647 となります。

一方でlong long 型の場合はint型である64bitのメモリが割り当てられるので、全く同じような考え方で、扱える数字の個数は $2^{64}$ で、最大値、最小値はそれぞれ、9,223,372,036,854,775,807 と -9,223,372,036,854,775,808 となるのです。

PR

https://developers.cyberagent.co.jp/blog/archives/44435/