初投稿です。投稿の練習を兼ねています。
ATCoder ABC334 のB問題 "Christmas Trees" で躓きました。B問題なのにやたら難しく、悔しかったので負数の除算・剰余算について考察してみました。
Python の場合
Python で次のコードを実行してみます。
print("-5//3=", -5//3)
print("-5%3=", -5%3)
結果はこうなります。「-5//3= -2」のあたり、直感的には少し違和感を感じます。
-5//3= -2
-5%3= 1
-5 〜 5 の範囲で結果を一覧にしてみるとこうなります。規則的に変化しており、負の数の除算・剰余算が上のような結果になった理由が納得できます。
i | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|---|---|---|---|
i//3 | -2 | -2 | -1 | -1 | -1 | 0 | 0 | 0 | 1 | 1 | 1 |
i%3 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 |
C++ の場合
C++ で次のコードを実行してみます。
cout << "-5/3= " << -5/3 << endl;
cout << "-5%3= " << -5%3 << endl;
gcc 13.2.0 の場合の結果はこうなります。直感的にはこちらのほうが合っているような気分になります。
-5/3= -1
-5%3= -2
ところが、-5 〜 5 の範囲で結果を一覧にしてみるとこうなります。
i | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|---|---|---|---|
i/3 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
i%3 | -2 | -1 | 0 | -2 | -1 | 0 | 1 | 2 | 0 | 1 | 2 |
i=0 の前後で除算・剰余算の振る舞いが不自然になっていて、正・負によって計算結果に連続性がありません。そもそもC言語の言語仕様では負数の除算についての定義が無く、実装依存とされてきた歴史からこのようになっているらしいです。現実には上のような振る舞いが C/C++言語の標準になっているようですが、連続した数列を扱うときに正・負で場合分けする必要が出てきたり、面倒なことが起こります。
動作の違いについてまとめると、Pythonの除算は常に値の小さい方(数直線では左側)に丸めるのに対して、C/C++の除算は0に近い方(数直線上では0に近い側)に丸める動きをする、と言えると思います。(AtCoderのsnuke氏の解説の受け売りです) Pythonは実用的、C/C++は教科書的な振る舞いとも言えるでしょうか?(ちょっと無理あり)
マクロ
対策として、Python と同じ振る舞いになるようにマクロを作りました。
// Pythonと同じ動きの除算
#define pydiv(a,b) ((0<(a)&&0<(b)||(a)<0&&(b)<0) ? (a)/(b) : (0<(b)) ? ((a)-(b)+1)/(b) : ((a)-(b)-1)/(b))
// Pythonと同じ動きの剰余算
#define pymod(a,b) ((0<(a)&&0<(b)||(a)<0&&(b)<0) ? (a)%(b) : ((a)%(b)+(b))%(b))
このマクロを使って試してみます。
for (int i=-5; i<=5; i++) {
cout << i << " " << pydiv(i, 3) << " " << pymod(i, 3) << endl;
}
結果は下のようになり、Python と同じ振る舞いになりました。
i | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|---|---|---|---|
i/3 | -2 | -2 | -1 | -1 | -1 | 0 | 0 | 0 | 1 | 1 | 1 |
i%3 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 |
除算については floor() 関数などもあるので、別の良い方法もあるかもしれません。
例題
さて、躓いたAtCoderのABC334のB問題です。
解説動画では正・負を考慮せずに済むように「座標系をずらす」工夫で面倒な処理を回避していますが、あまり深く考えず、次のように書いて正答できました。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pydiv(a,b) ((0<(a)&&0<(b)||(a)<0&&(b)<0) ? (a)/(b) : (0<(b)) ? ((a)-(b)+1)/(b) : ((a)-(b)-1)/(b))
#define pymod(a,b) ((0<(a)&&0<(b)||(a)<0&&(b)<0) ? (a)%(b) : ((a)%(b)+(b))%(b))
int main()
{
ll A, M, L, R;
cin >> A >> M >> L >> R;
L -= A;
R -= A;
cout << pydiv(R,M) - pydiv(L-1,M) << endl;
return 0;
}
追記
コメント欄で @Nabetani さんからinline関数を使った実装を提案いただきました。C++の作法としてはこちらのほうが良いかもしれません。改行を省いて各1行で書いておけば競プロ用のヘッダーファイルに書いておいても邪魔になりません。
@Nabetani さん、ありがとうございました。
template< typename T > inline auto pymod2( T const & a, T const & b ) -> decltype(a%b) { return (a%b+b)%b; }
template< typename T > inline auto pydiv2( T const & a, T const & b ) -> decltype(a/b){ return (a-pymod2(a,b))/b; }
また、@fujitanozomu さんからは次のような実装を提案いただきました。
template< typename T >
inline T pymod3(T a, T b) {
return ((a ^ b) < 0) && a % b != 0 ? a % b + b : a % b;
}
template< typename T >
inline T pydiv3(T a, T b) {
return ((a ^ b) < 0) && a % b != 0 ? a / b - 1 : a / b;
}
どちらのご提案も勉強になりましたが、自分自身のテンプレートには、最初に書いた自分のマクロを採用することにしました。他人に強く勧めるものではありませんが、「結果が負になるときは数直線上で左側に丸める」という自分の思考に一番近いからです。コメントをいただいたお二人には感謝申し上げます。