実際の問題はこちらからご覧ください。
【AtCoder Beginner Contest 237】A – Not Overflow
この問題のポイント
整数の範囲判定が中心となりますが、問題文から抽出すべき重要な点は、対象となる整数が具体的にどの範囲に収まるべきかという条件です。
具体的には、整数Nが−2の31乗−2の31乗以上かつ2の31乗未満である必要があります。この範囲はプログラミングにおいてよく出くわす32ビット符号付き整数の範囲になる。
Pythonの場合、整数の扱いにおいてオーバーフローの心配がないため、直接的に数値を比較することで範囲内かどうかを判断できる。
実装方法
１. まず整数 n を入力として受け取る
２. 次に n が-2の31乗以上かつ2の31乗未満であるかどうかを判定
３. 条件を満たす場合は”Yes”を、そうでない場合は”No”を出力
Pythonによる解答
このアルゴリズムの計算量は、O(1)
n = int(input())
max = pow(2, 31)
min = -max
if (min <= n and n < max):
print('Yes')
else:
print('No')maxとminの変数を一度しか記述していないので、直書きした方がシンプルでよかったと後で思いました。
n = int(input())
if -2**31 <= n < 2**31:
print("Yes")
else:
print("No")
以下は、Pythonでは考慮しなくてよかったオーバーフロー対策をC++で実装したコードです。
#include <bits/stdc++.h>
using namespace std;
int main(void) {
long long n;
long long m = (long long)1 << 31;
//long long m = 1 << 31; では右辺が (int)1<<31 として計算されるため
//オーバーフローし(=-(2 の31 乗)になってしまう)、その値が long long 型に直され m に代入されてしまう。
//long long m = 2147483648; という記述はint型を扱っていなから問題ない
cin >> n;
if ((-m <= n) && (n < m))cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}C++において、リテラル1はデフォルトでint型として扱われる。そのため、1 << 31のような操作を行うと、int型の範囲を超える可能性がある。32ビットの符号付き整数であるint型では、最大値は2の31乗−1です。
したがって、1 << 31と直接計算すると、理論上は2の31乗になるべきですが、int型の範囲を超えてしまい、結果としてオーバーフローが発生する。このオーバーフローは、意図しない負の値を生じさせてしまう。
この問題を回避するために、コードでは1をlong long型に明示的にキャストしている。long long型は少なくとも64ビットの整数を保持できるため、1 << 31の計算結果も安全に扱うことができます。
このキャストにより、シフト演算がlong long型のコンテキストで実行され、オーバーフローを回避しながら意図した値である2の31乗を正しく計算できる。
