競技プログラミングにおける数値の扱い

はじめに

この記事は競技プログラミング研究月間に書かれたものです。

AtCoderのC++ (gcc) 環境を想定しています。サンプルコードの実行はpractice contestのコードテストで行いました。

DifficultyはAtCoder Problems、yukicoderの問題の参考Difficultyはyukicoder problems、トリッキー問題コンテストの参考Difficultyはatcoder-standings-difficulty-analyzerから取得した値を使用しています。

本記事の構成

最初に、競技プログラマが数値の扱いを学ぶ意義について記述します。次に、コンピュータの数値表現について軽く説明します。

その後の章では、整数と浮動小数点数それぞれについて例題を交えながら注意点を解説します。

数値の扱いを学ぶ重要性

オーバーフローなど、数値の扱いに起因するバグはよくあります。数値の扱いを学べばどこが怪しいか当たりを付けることができるようになります。

また、オーバーフローや誤差に関する問題がABCで出題されることがあります。

• ABC169-B Multiplication 2 (Difficulty: 352)
• ABC169-C Multiplication 3 (Difficulty: 597)
• パナソニックプログラミングコンテスト2020-C Sqrt Inequality (Difficulty: 701)

これらの問題は、コンピュータで数値がどのように扱われているか知っていれば解けますが、知らずに解くのは困難な問題です。コンテストで良い成績を取るためにも重要です。

コンピュータの数値表現

コンピュータはあらゆる数値をそのまま扱えるわけではなく、一定の長さのデータとして扱っています。基本的な数値型はint型などの整数型とdouble型などの浮動小数点数型があります。

整数

コンピュータの整数の表現には符号付き整数と符号なし整数があります。

$k$ bitの符号なし整数は整数を $2^k$ で割った余りです。表せる範囲は $0$ から $2^k-1$ です。

符号付き整数は、AtCoderを含むほとんどの処理系では2の補数表現を用いています。この場合、$k$ bitの符号付き整数で表せる範囲は $-2^{k-1}$ から $2^{k-1}-1$ です。

signed が付く整数は符号付きで、unsigned が付く整数は符号なしです。

signed も unsigned も付かない short、int、long、long long は符号付き整数です。

char

8bit整数です。signed や unsigned を付けない char は処理系によって符号付きか符号なしか違います。AtCoderでは符号付きです。

符号付きでは-128から127まで、符号なしでは0から255までの値が表せます。

名前の通り文字を扱うのがメインなので、std::cout を使うと数値ではなく文字として出力されます。

short

16bit整数です。符号付きでは-32768から32767まで、符号なしでは0から65535までの値が表せます。

int

（禁断の #define int long long を使っていなければ）32bit整数です。符号付きでは-2147483648から2147483647$(>2\times10^{9})$まで、符号なしでは0から4294967295までの値が表せます。

特に、絶対値が $10^9+9$ 以下に収まる整数同士の加減算の結果はint型に収まります。

long

AtCoderでは64bit整数です。ジャッジによっては32bit整数のこともあるので使わないのが無難です。

long long

64bit整数です。符号付きでは-9223372036854775808から9223372036854775807$(>9\times10^{18})$まで、符号なしでは0から18446744073709551615までの値が表せます。

制約に $10^9$ や $10^{18}$ が多用される理由は、演算を行ってもlong longに収まるからです。

intXX_tとuintXX_t

int64_t のようにbit数を指定して宣言することができます。XXに指定できる数字は8,16,32,64です。intXX_t は符号付き整数、uintXX_t は符号なし整数です。

__int128_tと__uint128_t

gccの拡張です。128bit整数です。直接入出力することは出来ません。

浮動小数点数

AtCoderを含むほとんどの処理系は IEEE 754 に準拠しています。IEEE 754 では小数を符号、指数、仮数に分け、$符号 \times 仮数 \times 2^{指数}$の形式で表します。long double以外の型では基本的に $仮数=1+（仮数部の整数表現）/2^{仮数部のbit数}$ として表し、仮数部の最上位bitが無駄にならないようにしています。

float

AtCoderでは単精度浮動小数点数（符号1bit、指数8bit、仮数23bit、計32bit）です。有効数字は約7桁です。

double

AtCoderでは倍精度浮動小数点数（符号1bit、指数11bit、仮数52bit、計64bit）です。有効数字は約16桁です。

long double

AtCoderでは拡張倍精度浮動小数点数（符号1bit、指数15bit、仮数64bit、計80bit）です。この型のみ仮数部分の最上位のbitの上の桁がありません。有効数字は約19桁です。

__float128

gccの拡張です。四倍精度浮動小数点数（符号1bit、指数15bit、仮数112bit、計128bit）です。有効数字は約34桁です。直接入出力することは出来ません。

数値リテラルの扱い

1.2 、1.0 、1. のように小数点を含む、もしくは 1e9 のような指数表記の数は浮動小数点数として扱われます。1 のようにいずれも含まない場合は整数として扱われます。

浮動小数点数では末尾に F が付いていればfloat、何もなければdouble、L が付いていればlong doubleです。

末尾に何もついていない整数は、intに収まるならint、収まらないならlong、それにも収まらないならばlong longと解釈されます。末尾に L が付いていればlong、LL が付いていればlong longと解釈されます。末尾に U がついている整数は符号なし整数です。U は L や LL と同時に使用できます。

整数型の限界

整数型では誤差なく計算することができますが、表せる値の範囲に制限があります。

オーバーフロー

数の型で表せる数の範囲を超えることをオーバーフローといいます。

C++では符号付き整数型のオーバーフローが発生した場合の動作は未定義、つまり（オーバーフロー前の動作を含めて）何が起こるか一切分かりません。$k$ bitの符号なし整数でオーバーフローが発生した場合は結果を $2^k$ で割った余りになります。

例題

ABC169-B Multiplication 2 (Difficulty: 352)

$A_i$ は最大 $10^{18}$ なので、$A_1 \times A_2$ は最大 $10^{36}$ です。$10^{36} > 2^{64}$ なので、掛け算1回でもオーバーフローします。128bit整数を使っても $A_1 \times A_2 \times A_3$ は最大 $10^{48} (>2^{128})$ でオーバーフローします。

符号なし整数であってもオーバーフローした後は $10^{18}$ より大きいとは限らないので、単純に計算する方針では正解できません。$10^{18}$ を超えたかどうかの判定を除算で行うと64bit整数でもACできます。

多倍長整数

Pythonなどの言語ではデフォルトで多倍長整数を使うことができます。多倍長整数は計算に時間がかかりますがオーバーフローの心配がありません。

最低でも桁数に比例する時間がかかるので、多倍長整数で全て計算しようとすると $\Omega(N^2)$ となり間に合いませんが、$10^{18}$ を超えるかどうか判定するのには使えます。

初級者まではC++よりPythonが有利と言われる理由の一つです。

総和を求めるときのオーバーフロー

int型同士の乗算は1回でもオーバーフローの原因になるので見つけやすいですが、総和を求めるときにオーバーフローするパターンがあります。

コード

#include <iostream>
#include <vector>

int main() {
  int n = 100000;
  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    a.at(i) = i;
  }

  int s = 0;
  for (int i = 0; i < n; i++) {
    s += a.at(i);
  }

  std::cout << s << std::endl;
}

結果（常にこうなる保証はありません）

704982704

正しくない結果が出ました。何がおかしかったのでしょうか。

a に格納する段階では何も問題はありません。問題は s です。s は最終的に $5 \times 10^9$ 程度になるのでオーバーフローします。

s をlong long型にしてみましょう。

#include <iostream>
#include <vector>

int main() {
  int n = 100000;
  std::vector<int> a(n);
  for (int i = 0; i < n; i++) {
    a.at(i) = i;
  }

  long long s = 0;
  for (int i = 0; i < n; i++) {
    s += a.at(i);
  }

  std::cout << s << std::endl;
}

結果

4999950000

総和が正しく求まりました。

std::accumulate

配列などのコンテナの総和などを計算できる std::accumulate という関数があります。簡潔に書けて便利ですが、オーバーフローに注意する必要があります。

std::accumulate の戻り値の型は3つ目の引数の型です（cpprefjpのリファレンス）。3つ目の引数に0を使っていると、0はint型なのでオーバーフローすることがあります。

コード

#include <iostream>
#include <numeric>
#include <vector>

int main() {
  std::vector<long long> a(100000);
  for (int i = 0; i < 100000; i++) {
    a.at(i) = i;
  }
  std::cout << std::accumulate(a.begin(), a.end(), 0) << std::endl;
}

結果

704982704

0 を 0LL に書き換えるか、int64_t() のような記法を使うか、std::reduce を使うと問題を解決できます。std::reduce は初期値の設定がなくても総和を計算できます（cpprefjpのリファレンス）。

0LL に書き換えたコード

#include <iostream>
#include <numeric>
#include <vector>

int main() {
  std::vector<long long> a(100000);
  for (int i = 0; i < 100000; i++) {
    a.at(i) = i;
  }
  std::cout << std::accumulate(a.begin(), a.end(), 0LL) << std::endl;
}

結果

4999950000

int64_t() に書き換えたコード

#include <iostream>
#include <numeric>
#include <vector>

int main() {
  std::vector<long long> a(100000);
  for (int i = 0; i < 100000; i++) {
    a.at(i) = i;
  }
  std::cout << std::accumulate(a.begin(), a.end(), int64_t()) << std::endl;
}

結果

4999950000

std::reduce に書き換えたコード

#include <iostream>
#include <numeric>
#include <vector>

int main() {
  std::vector<long long> a(100000);
  for (int i = 0; i < 100000; i++) {
    a.at(i) = i;
  }
  std::cout << std::reduce(a.begin(), a.end()) << std::endl;
}

結果

4999950000

特殊なオーバーフロー

トリッキー問題コンテスト-A 整数割り算 (参考Difficulty: 1899)
2の補数表現を用いている場合、表現できる最小値と最大値の絶対値は違います。符号付き整数では $-2^{63}$ を扱うことができますが、$2^{63}$ はオーバーフローします。このコーナーケースを処理できればACできます。

浮動小数点数と誤差

浮動小数点数は幅広い数を表すことができますが、誤差が常につきまといます。誤差の扱いは奥が深いです。

切り上げ・切り捨てと比較

ABC169-C Multiplication 3 (Difficulty: 597)

見かけの割にDifficultyが異常に高い問題です。単純に掛け算するとWAになります。

コンピュータでは0.1などは無限小数なので、どんなに高精度な型を用いても型に応じた誤差が発生します。結果として、ちょうど整数になるときに結果が少し小さい値になってしまいWAとなります。等価判定にある程度の余裕を持たせて十分な精度の型で計算すればACできます。この問題では18桁程度の有効数字があればいいので、long double型以上の精度の型で0.005の余裕を持たせればACが得られます（C++コード）。

より簡単に解く方法としては、整数に直してから計算する方法があります（Pythonコード）。

桁落ち

2つの正の実数 $a, b$ とし相対誤差を $\epsilon$ とすると、それぞれの絶対誤差は $a\epsilon, b\epsilon$ となります。値の範囲はそれぞれ $a \pm a\epsilon, b \pm b\epsilon$ です。

$a, b$ に四則演算を行った後の相対誤差について考えてみましょう。$\epsilon$ の2乗以上の項は小さいので無視します。

加算では、結果は $(a+b) \pm (a+b)\epsilon$ の範囲に入るので相対誤差は変わりません。
減算では、結果は $(a-b) \pm (a+b)\epsilon$ の範囲になるので相対誤差は $\frac{a+b}{a-b} \epsilon$ となり、$a$ と $b$ が近いときに精度が低下します。
乗算では、結果は $ab \pm 2ab\epsilon$ の範囲に入るので相対誤差は大きくは変わりません。
除算では、結果は $a/b \pm 2(a/b)\epsilon$ の範囲に入るので相対誤差は大きくは変わりません。

以上から、近い数値同士の減算を行うと相対誤差が大きくなることが分かります。これを桁落ちと言います。

負数が入る場合は加減算が逆になったり結果の符号が変わったりしますが、本質的な影響はありません。

例題

トリッキー問題コンテスト-B 一変数方程式 (参考Difficulty: 2543)
yukicoder No.955 ax^2+bx+c=0 (参考Difficulty: 1515)

yukicoderの問題は自作問題です。出題後既出だと判明しました。トリッキー問題コンテストのほうが入力の制約が大きく、yukicoderの問題のほうが許容誤差は厳しいです。

$a \neq 0$ の場合を考えます。二次方程式の解の公式
$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$
を用いて解を求めるとWAになります。

$b$ の絶対値が大きく $ac$ の絶対値が小さいとき、$\sqrt{b^2-4ac}$ は $|b|$ に近くなります。$b>0$ のときは加算で、$b<0$ のときは減算で桁落ちが発生します。

桁落ちを回避するには、桁落ちしないほうの解を求めてから、解と係数の関係 $x_1 x_2 = \frac{c}{a}$ を用いてもう一方の解を求めればよいです。

記法に関する注意

この章では数値や演算子などの記法に関する注意点を紹介します。

整数同士の除算と剰余演算

C++では 整数 / 整数 は整数になります。

コード

#include <iostream>

int main() {
  std::cout << 10 / 3 << std::endl;
}

結果

3

AtCoderでは、端数は0方向に丸められます。

結果が負になる除算のコード

#include <iostream>

int main() {
  std::cout << -10 / 3 << std::endl;
}

結果

-3

剰余演算は a % b = a - a / b * b が成り立つように決められているので、負数の剰余演算を行うと結果が負になることがあります。

負数の剰余演算のC++コード

#include <iostream>

int main() {
  std::cout << -1 % 1000000007 << std::endl;
}

結果

-1

Pythonの整数同士の除算

Pythonでは 整数 / 整数 は浮動小数点数になります。

Pythonの 整数 / 整数 のコード例

print(10 / 3)

結果

3.3333333333333335

整数型にするためには 整数 // 整数 と記述しましょう。こちらは負の無限大方向への丸めです。

Pythonの 整数 // 整数 のコード例

print(10 // 3)

結果

3

Pythonの 整数 // 整数 のコード例

print(-10 // 3)

結果

-4

負数の剰余演算のPythonコード

print(-1 % 1000000007)

結果

1000000006

size()に注意！

size() 関数の結果の型は size_t です。これは符号なし整数型です。符号なし整数型は同じサイズの符号付き整数型より強いので、演算に使うとバグの原因になることがあります。競技プログラミングでは size() 関数の結果をキャストするのがおすすめです。

指数表記

多くの言語には指数表記が存在します。$10^9+7$ は 1e9+7 のように書くことができます。確かめてみましょう。

コード

#include <iostream>
long long mod = 1e9 + 7;
int main() {
  std::cout << mod << std::endl;
}

結果

1000000007

うまくいきました。

では、無限大を表すのに $10^{18}+1$ を使いたいとき、1e18+1で良いでしょうか？試してみましょう。

コード

#include <iostream>
long long inf = 1e18 + 1;
int main() {
  std::cout << inf << std::endl;
}

結果

1000000000000000000

$10^{18}+1$ のつもりが $10^{18}$ になってしまいました。なぜこうなったのでしょうか？

指数表記で書かれたリテラルはdouble型です。1はint型なので、double型とint型の加算になり、結果はdouble型になります。double型では $2^{53}$ を超える奇数は表せないので、近い数 $10^{18}$ に丸められてしまいます。$10^9+7$ のときにうまくいったのは $10^9+7<2^{53}$ だからです。

long longにキャストしてから演算してみましょう。

コード

#include <iostream>
long long inf = (long long)1e18 + 1;
int main() {
  std::cout << inf << std::endl;
}

結果

1000000000000000001

想定した動作になりました。$10^{18}$ は $5^{18} \times 2^{18}$ と表すことができ、$5^{18} < 2^{53}$ なので 1e18 は誤差が出ません。それ以降は全てlong long型なので、全体が正しく計算されます。

もう一つの方法として、long double型を使う方法があります。浮動小数点数リテラルの後ろにLを付けるとlong double型として扱われます。long double型では $2^{64}$ 以下の整数は誤差なく扱えるので、$10^{18}+1$ でも大丈夫です。

コード

#include <iostream>
long long inf = 1e18L + 1;
int main() {
  std::cout << inf << std::endl;
}

結果

1000000000000000001

出力桁数

C++で浮動小数点数を出力するとき、デフォルトの桁数では足りないことが多いので出力桁数を増やしましょう。printf でフォーマットを指定して出力するか、std::setprecision を使って出力桁数を変更しましょう。

std::cout で桁数を指定しないコード

#include <iostream>

int main() {
  std::cout << 10.0 / 3.0 << std::endl;
}

結果

3.33333

全体の桁数が6桁になります。

printf を長さ指定なしで用いたコード

#include <cstdio>

int main() {
  printf("%f\n", 10.0 / 3.0);
}

結果

3.333333

小数点以下の桁数が6桁になります。

printf の %g をそのまま用いたコード

#include <cstdio>

int main() {
  printf("%g\n", 10.0 / 3.0);
}

結果

3.33333

全体の桁数が6桁になります。

std::setprecision を用いたコード

#include <iostream>
#include <iomanip>

int main() {
  std::cout << std::setprecision(16) << 10.0 / 3.0 << std::endl;
}

結果

3.333333333333333

全体の桁数が16桁になります。

printf を小数点以下の桁数を指定して用いたコード

#include <cstdio>

int main() {
  printf("%.16f\n", 10.0 / 3.0);
}

結果

3.3333333333333335

小数点以下の桁数が16桁になります。

printf の %g を桁数を指定して用いたコード

#include <cstdio>

int main() {
  printf("%.16g\n", 10.0 / 3.0);
}

結果

3.333333333333333

全体の桁数が16桁になります。

基本方針

• int同士の演算はオーバーフローに注意
  • 合計を求めるときは特に注意
  • 添え字以外にintを使わない方針は有効
  • 全部long longにする方針もある
• 浮動小数点数を避けられるのならそうする
• 値が近い浮動小数点数同士の減算、絶対値が近い異符号の浮動小数点数同士の加算は避ける
• 浮動小数点数同士の比較はある程度の誤差を許容する

浮動小数点数回避の例題

パナソニックプログラミングコンテスト2020-C Sqrt Inequality (Difficulty: 701)

問題文が非常にシンプルな問題です。

式変形すると整数だけで扱うことができます。

まとめ

競技プログラミングでも数値の扱いを学ぶのは重要です。数値の扱いでWAなどが出たとき、なぜそうなったのか分かるようになりましょう。そして数値を正しく扱えるようになりましょう！