【競プロ/C++/ABC334-B問題】除算・剰余算のマクロを作った

初投稿です。投稿の練習を兼ねています。

ATCoder ABC334 のＢ問題 "Christmas Trees" で躓きました。B問題なのにやたら難しく、悔しかったので負数の除算・剰余算について考察してみました。

# Python の場合

Python で次のコードを実行してみます。

~~~Python:Python
print("-5//3=", -5//3)
print("-5%3=", -5%3)
~~~

結果はこうなります。「-5//3= -2」のあたり、直感的には少し違和感を感じます。

~~~txt:結果
-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++ で次のコードを実行してみます。

~~~C++:C++
    cout << "-5/3= " << -5/3 << endl;
    cout << "-5%3= " << -5%3 << endl;
~~~

gcc 13.2.0 の場合の結果はこうなります。直感的にはこちらのほうが合っているような気分になります。

~~~txt:結果
-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++言語の標準になっているようですが、連続した数列を扱うときに正・負で場合分けする必要が出てきたり、面倒なことが起こります。

動作の違いについてまとめると、<font color="Red">Pythonの除算は常に値の小さい方（数直線では左側）に丸めるのに対して、C/C++の除算は０に近い方（数直線上では0に近い側）に丸める動きをする、</font>と言えると思います。（AtCoderのsnuke氏の解説の受け売りです） Pythonは実用的、C/C++は教科書的な振る舞いとも言えるでしょうか？（ちょっと無理あり）

# マクロ

対策として、Python と同じ振る舞いになるようにマクロを作りました。

~~~C++:C++
// 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))
~~~

このマクロを使って試してみます。

~~~C++:C++
    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問題です。

https://atcoder.jp/contests/abc334/tasks/abc334_b

解説動画では正・負を考慮せずに済むように「座標系をずらす」工夫で面倒な処理を回避していますが、あまり深く考えず、次のように書いて正答できました。

~~~C++:abc343_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 さん、ありがとうございました。

~~~C++:C++
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 さんからは次のような実装を提案いただきました。

~~~C++:C++
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;
}
~~~

どちらのご提案も勉強になりましたが、自分自身のテンプレートには、最初に書いた自分のマクロを採用することにしました。他人に強く勧めるものではありませんが、「結果が負になるときは数直線上で左側に丸める」という自分の思考に一番近いからです。コメントをいただいたお二人には感謝申し上げます。