B - Integer Division 解説 by Nyaan
この問題は、競技プログラミングに頻出である 切り捨て除算 を正しく行うことができるか?を問うている問題です。この問題が解けなかった / 長い時間を費やしてしまった という人はこの際に是非正しい切り捨て除算のやり方を覚えてください。
細かい解説は後に書くとして、ポイントは大きく \(2\) つあります。
1. 小数を使わない
これは Python ユーザーの方にありがちなミスですが、切り捨て除算を C = int(A / B)
のように小数を経由して計算する人がいます。これは一見正しい計算ができているようですが、 将来的にバグの原因となる危険な計算方法 なので出来るだけ控えた方が良いです。
Python の float
や C++ の double
のような一般的な浮動小数点数型は高々 (\(2\) 進 \(53\) 桁) \(\simeq\) (\(10\) 進 \(16\) 桁) 程度の精度しか持ちません。よって、\(10^{18}\) のような大きい数を計算する時には誤差が発生して正しい計算が出来なくなります。
n1 = 10**18 - 42
n2 = int(float(n1))
print(n1) # 999999999999999958 が出力される
print(n2) # 1000000000000000000 が出力される
2. 負数の除算に注意する
この問題では\(X\) の範囲が \(-10^{18}\) 以上となり、割られる数が負の場合の除算が発生します。一見割られる数が正の場合と変わらないようですが、実は 負数の除算はいくつか定義があり、プログラム言語によって定義が異なる という大きな問題があります。
- 詳しい話は以下で説明しますが、例えば \(-24\) を割られる数、 \(10\) を割る数として整数除算した時の答えは言語によって \(-2\) になったり \(-3\) になったりします。
もしも「自分が思っていた負数の除算の挙動」と「実際の除算の挙動」が異なっていた場合、人によっては WA が出た時にどこが間違っているのか気づかず苦労してしまうかもしれません。
これらの例のように、自分が思っていた動作と正しい動作が異なるのに気づかずに「こう書けばきっと正しく動くはず」と思い込んで実装してバグを埋め込んでしまう、というのはプログラムを書く上で本当によくあるミスだと思います。
プログラマーに関するミームとして「プログラムは思った通りには動かない。書いた通りに動く」という言葉があります。これは言い換えると「うっかり間違って書いてしまうと思い通りに動かない」という話である意味当たり前のことですが、世の中のバグの大半はこうした「思い込み」によってできたものなのを考えると、なかなか侮れない言葉だと思います。
また、競技プログラミングでの経験の中で、もしも WA が出た時に、「自分が思った挙動」と「実際の挙動」を擦り合わせてどこが間違っているのかを発見できる能力を身に着けられると、実装できるプログラムの幅が大きく広がると思います。
さて、そろそろ詳しい解説に入りましょう。2. の理由から、この問題は言語によって適切な答え方が変わる問題です。 解説では C++ と Python での解法を載せますが、他の言語を使用している方は上の「提出結果」から上位の解答を読んでみるなどしてやり方を調べることを推奨します。
Python
Python では以下のように簡潔に書くことができます。
X = int(input())
print(X // 10)
なぜならば、Python の切り捨て除算演算子 //
は、分数に対して問題文に定義されている通りの floor 関数 \(\lfloor \ \rfloor\) を適用したものになっているからです。
print(47 // 10) # 4 が出力される
print(-24 // 10) # -3 が出力される
よって、//
を使って自然に実装すればこの問題を解くことができます。
一般に、A
を B
で切り捨て除算したい場合も、A // B
と書けば正しく動作します。普段 int(A / B)
と実装していた人はこれを機に A // B
を使用することを推奨します。
C++
問題は C++ の場合です。 C++ では /
で切り捨て除算を行うことができますが、実はこれをそのまま使うだけではうまくいきません。
試しにサンプルを実行してみると次のようになります。
#include <iostream>
#include <iostream>
using namespace std;
int main() {
cout << 47 / 10 << endl; // 4 が出力される
cout << -24 / 10 << endl; // -2 が出力される
}
どうして -24 / 10
が -2
になるのかというと、C++ (正確には C++11 以降) における除算は「小数部分を無視した数学的な商」を計算しているからです。
- 例えば
-24/10
の場合、 \(-24/10 = -2.4\) で、\(.4\) の部分を取り除くと \(-2\) となりこれが答えとなります。
以上の理由から、 C++ の整数除算では、「割られる数が負である」 + 「余りが発生している」場合に本来切り捨てられるべき部分が切り上げられてしまいます。よってそのようなケースでは出てくる答えに \(1\) を引けば正しい答えを求めることができます。
以上の話をまとめると、次のような実装をすればこの問題を AC することができます。
#include <iostream>
using namespace std;
int main() {
long long X;
cin >> X;
if (X < 0 and X % 10 != 0) {
cout << X / 10 - 1 << "\n";
} else {
cout << X / 10 << "\n";
}
}
別解として剰余演算子 %
を用いる方法もあります。 C++ では %
は (a / b) * b + a % b = a
を満たす演算子として定義されているので、切り上げが発生するのは 「a % b
が負である」ときのみであるとわかります。
よって次のような書き方をしてもこの問題を AC することができます。
#include <iostream>
using namespace std;
int main() {
long long X;
cin >> X;
cout << X / 10 - (X % 10 < 0) << "\n";
}
一般に、A
を B
で切り捨て除算したい場合は、
A,B
ともに正の場合A / B
A,B
が負を取り得る場合A / B - (A % B < 0)
で上手くいくので、これを機に覚えておくとよいでしょう。
解説は以上となります。普段とは少し毛色の異なる難しさを含んだ問題だったと思いますが、切り捨て除算はこれまでも、そしてこれからも何度も出てくる演算だと思うので是非ともここで正しいやり方を覚えていただけるとありがたいです。
投稿日時:
最終更新: