【競プロ】数

ここでは、数学の世界でもプログラミングの世界でも、最も基本的なものである「数」について整理していきます。競プロ 記事の一覧はこちら

【広告】

整数

$0$ に $1$ を何度か足して得られる数、つまり、 $1,2,3,\cdots$ のことを、正の整数(positive integer) といいます。プログラミングの世界では、 $0$ に対して何度かインクリメントを行ったもの、と言い換えることもできます(オーバーフローを起こさない範囲で)。次のコードは、C++で正の整数を表示し続けるコードです。改行を入力するたびに正の整数を整数を順番に表示し、改行以外の文字を入力すると処理が終わります。

#include <iostream>
using namespace std;

int main() {
  int i = 0;
  string s = "";
  while (s == "") {
    i++;
    cout << i;
    getline(cin, s);
  }
  return 0;
}

$0$ から $1$ を何度か引いて得られる数、つまり、 $-1,-2,-3,\cdots$ のことを負の整数(negative integer) といいます。 $0$ に対して何度かデクリメントを行ったもの、と言い換えることもできます。次のコードは、上と同じ要領で負の整数を表示するC++のコードの例です。

#include <iostream>
using namespace std;

int main() {
  int i = 0;
  string s = "";
  while (s == "") {
    i--;
    cout << i;
    getline(cin, s);
  }
  return 0;
}

正の整数、負の整数と $0$ とを合わせて、整数(integer) といいます。

高校までの数学では、正の整数のことを自然数(natural number) と呼んでいました。しかし、大学以降は、自然数に $0$ を含めることもあります。特に、コンピュータの世界では、 $0$ を含めることが多いです。初期値や配列の最初の添え字も、ほとんどの言語では0となっているので、0 を出発点とするほうが自然だと考えられます。

こうした事情から、混乱を防ぐために、「自然数」という言葉を避けることがあります。自然数という言葉を使わない場合、 $1,2,3,\cdots$ を言いたいときには正の整数や正整数といい、 $0,1,2,3,\cdots$ のことを言いたいときには非負整数(non-negative integer) という言葉を使います。競プロの問題でも、これらの言葉が問題文で使われます。

【広告】

多くのプログラミング言語では、変数に整数を格納するために、特別な型が用意されています。C++でよく使われる型と扱える整数の範囲は次のようになっています。

int
-2147483648 ~ 2147483647
long long int
-9223372036854775808 ~ 9223372036854775807

簡単な問題であれば、int型で事足ります。扱える値の上限は、10桁の数で、1番上の位が2です。long long int型は、大きな数同士を掛ける場合などで使います。こちらの上限は、19桁の数で、1番上の位が9です。long long int型は、long long型ともいいます。

上限と下限の正確な値を知っておく必要はないですが、何桁くらいかは頭の隅に置いておきましょう。

競プロで、「32bit整数型で収まらない可能性がある」と注記されていることがあります。これは、int型の範囲に収まらない、ということです。こう言われている場合は、C++なら long long型を使いましょう。

プログラミング言語によって、型の扱いは異なります。競プロでは、大きな数を扱うこともあるので、扱える値の範囲を確認しておきましょう。

if文が使えるなら、AtCoder ABC 011 A – 来月は何月?ができるでしょう。また、文字の使い方がわかっていれば、AtCoder ABC 101 A – Eating Symbols Easyもできるでしょう。

小数

長さや重さなどを測るときには、 $0.1$ や $0.25$ のような単位1に満たない部分が発生することもあります。このような数を小数点を用いて表したものを、小数(decimal) といいます。$0.1$ は、単位1を10分割したものの1つ分、 $0.01$ は、100分割したものの1つ分を表します。

$3.14$ という小数に対して、1の部分を「小数第一位」といい、4の部分を「小数第二位」といいます。「小数第一位」のことを、「小数点第一位」と呼ぶこともあります。

コンピュータは、整数と小数とでは扱い方が異なるため、たいていは、それぞれに型が用意されています。C++では、上で紹介したように、整数に対してはint型やlong long型を使いますが、小数に対してはdouble型を使います。float型もありますが、競プロでわざわざ使う人は少ないです。

小数を整数型の変数に入れてしまうと、整数に変換されてしまう言語もあるので注意しましょう。例えば、C++では次のように整数になってしまいます。

#include <iostream>
using namespace std;

int main() {
  double d = 3.14;
  int i = 3.14;
  cout << d << "\n"; // 3.14と表示される
  cout << i << "\n"; // 3と表示される
  return 0;
}

double型で表すことができる数は、 $2.22507 \div 10^{308}$ から $1.79769 \times 10^{308}$ の範囲にある数と、これにマイナスをつけたものです。ただ、これは少し注意が必要です。この間の数をすべて表すことができるわけではありません。有効数字は、上から15桁程度で、精度に限界があります。

この理屈を理解するには、コンピュータが小数をどのように扱っているかを理解する必要があります。別の機会で説明する予定ですが、現時点では、小数を扱うときは小数を扱える型を使う、下の方の桁はあまり信用できない、と考えておけばOKです。

【広告】

数の出力

競プロでは、問題に対してコードを提出します。用意された入力値に対して、そのコードが正しい出力を返すかどうかで、コードが正しいかどうかが判断されます。この出力の仕方については、少し注意が必要です。

大きな整数や、桁数の多い小数を出力する場合、意図していない形式で出力されてしまうことがあります。環境によって結果は異なりますが、意図していない形式とは次のようなケースを言います。以下は、C++でのコードと出力例です。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
  cout << pow(11, 9) << "\n"; // 2.35795e+009 と表示される
  cout << 3.14159265 << "\n"; // 3.14159 と表示される
  cout << 0.00000314 << "\n"; // 3.14e-0.06 と表示される
  return 0;
}

pow(11, 9)は、11を9回掛けたものを表しています。掛け算は別の機会に見ることにしますが、ここではとても大きな数だと思っておけばOKです。

1つ目と3つ目の結果は、e が出てきて、数字じゃないみたいですね。2つ目は桁が勝手に減っています。競プロでは、このような出力では間違いとされてしまうケースがあります。すべての桁を全部表示するには、C++では、例えば次のように書きます。

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
  cout << (long long) pow(11, 9) << "\n";
  cout << fixed << setprecision(8) << 3.14159265 << "\n";
  cout << fixed << setprecision(8) << 0.00000314 << "\n";
  // 順番に、2357947691 3.14159265 0.00000314 と表示される
  return 0;
}

1つ目では、 long long型に変形しています。pow は、double型の値、つまり、小数を返すので、整数型に変換しています。2つ目と3つ目は、小数点以下を8桁まで表示する、という設定を行っています。

出力を調整する前に出てきた、e を用いた表現は、現時点では意味が分からないかもしれませんが、意味が分かるとすごく見やすくなります。このことは、将来、べき乗の部分で見ることにします。

おわりに

ここでは、競プロで扱う「数」について見てきました。整数と小数、そしてこれらを扱うための型や出力方法を見てきました。特に、競プロでは、アルゴリズムはあっているのに型が間違っているせいで、時間をロスしてしまうことがあります。もったいないので注意しましょう。