んぐのルーズリーフ

んぐの日記。最近はScrapBoxが主

トップ > テクノロジー > 【競プロ】intとlong longについて【C/C++】

【競プロ】intとlong longについて【C/C++】

テクノロジー

先日のABCでWAしました。

atcoder.jp

理由はlong long型を使っていなかったからです。

定期的にこのミスをやらかすのですが、なんで常にlong long型を使うんじゃなくて、「基本的にはintで、必要があればlong long」というスタンスをとっている人が多いんだろう…。と疑問に思いました。本記事でこの問題に決着をつけたいと思います。

僕はAtCoder以外の競プロコンテストにほとんど参加していないので、その立場から書きます。

基本的には「美学」？

この件について検索すると、次のツイートがヒットしました。

この情報を認めればlong longを必要以上に使わないのは「気持ちの問題」ということになります。 確かに私もintで済む問題でlong longを使うことになんとなく抵抗感を覚えます。


メリットを整理

少し両者の特性を整理してみましょう

intを使うメリット

  • SIMDが効きやすくなる（SIMD: 一つの命令を同時に複数のデータに適用し、並列に処理する方式）
  • メモリ量が削減できる
  • キャッシュに乗るデータの量が増え高速になる


long longを使うメリット

  • 大きな数字でも格納することができるようになる
    • オーバーフローエラーが回避できる
    • 具体的には9223372036854775807 \simeq 9.2 \times 10^{18}です（かなり大きいですね…！）
    • int型は2147483647 \simeq 2.1 \times 10^{9}です（結構あっという間に到達してしまいます）


概ねこのように考えて良いのではないでしょうか。


ちなみに、これを書くにあたって結構Google検索しましたが、 「long longを使うと速度的に間に合わなくなっちゃう問題があるよ！」と主張している記事は見当たらず、 せいぜい「定数倍改善にはなるね～」という主張くらいでした。


「お気持ち」の整理

これは個人的なお気持ちなので、人によっては他の理由でlong longを嫌っているかもしれません。

  • なんとなく必要以上にメモリを食ってる感じが嫌だ
  • たとえ正誤に関わらないくらい微々たる差でも高速化したい
  • C問題以上ならまだしもA問題やB問題でlong longを使うのは気に食わない
  • 宣言時の見た目がなんか嫌だ
    • using ll = long longしている人が多いと思いますが、皆さんはどうでしょうか？
    • ちなみに私はusing lint = intとしています
  • なぜか「十分な精度で計算している」ということに対する気持ちよさ、快さは感じないことの方が多い
    • 気持ちよく感じることもある
  • long long型の変数でvector配列のサイズ数を指定するのは怖い
  • long longを使う問題ではfor文の i の型に戸惑う
    • その他、intでも十分な他の変数の型をどうしようか迷う


気持ちの問題なら…

C++11からstd::int32_t、std::int64_tという型が定義されました。これはそれぞれ32bit/64bitの幅を保証した符号付き整数型です。 実はintやlong longが実際何bitかは処理系依存なのでこういうものが定義されています。

これを使えば「気持ちの面」が解消される人ももしかしたらいるかも…？ （自分が挙げた「速度」とか「必要以上のメモリ」の解決には何も役立ちませんが…）

# include <bits/stdc++.h>
using namesapce std;
// using int64 = int64_t するのもいいかも？
int main()
{
    int64_t a, b;
    cin >> a >> b;
    int64_t ans;
    ans = solve(a, b);
    cout << ans << endl;
    return 0;
}

…どうでしょうかね

悪魔の#define int long long

intをlong longに置き換えてしまう非常に強力なマクロです。long longやllなどという見た目が嫌な人はこういう方法を取るのもありだと思います。 ただし、C++的には予約語をdefineするのは未定義動作なので注意してください。GCCでは認められています。

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

// int main()と書くとエラー
signed main()
{
    int a, b;
    cin >> a >> b;
    int ans;
    ans = solve(a, b);
    cout << ans << endl;
    reutnr 0;
}


類似ケース

似たようなケースとしてv[0]とv.at(0)が挙げられると思っています。 少なくともAtCoderにおいてはどちらでも速度的に問題になることはほぼないのでatを使うべきなはずです。 しかし、見た目の問題や微々たる速度面、そして「お気持ち」で[]を選択している人も多いと思います。

ちなみに僕はこの手のミスで困った記憶がないのと、どうしてもv[0]という見た目から外れるのが嫌で[]を使っています。


総括

美学と実用…折り合いが難しいですが、僕の結論は以下の通りです。

  • A問題B問題でも64bit整数型を使う
    • しばらく使っても気持ち悪さをずっと感じるようだったら32bit整数型に戻す
  • C問題以上では64bit整数型を常に使う
  • using int32 = int32_tとusing int64 = int64_tを行い、この2つを使う
  • ついでにusing float32 = floatとusing float64 = doubleとusing float128 = long doubleを行い、これを使う
  • いろいろ書いたけど本当は実力をつけて必要なサイズの見積もりをきちんと行い適切な型を選択するのが一番良い、ということは頭に入れておく

明らかにint型で間に合う問題（特にグラフ系）でlong long型を使うのはかなり心苦しいんですけどね……。 ひとまず僕の中のint-long long戦争は一旦ケリをつけることにします。