ABC275 B問題（ABC-DEF）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）275 のB問題をC++とPythonで解いてみました。ABC275は、2022年10月29日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 ABC-DEF（Difficulty : 147）

問題はリンク先をご覧ください。

ABC275 B問題 ABC-DEF

剰余を求める計算を行います。オーバーフローに配慮する必要があります。AtCoder Problems による Difficulty は、147 でした。

解答案

問題を解く方針を書きだします。

• 6個の変数を読む。
• （オーバーフローに気を付けて）演算を行う。
• 演算結果を出力する。

オーバーフローの扱いは、プログラミング言語によって異なります。言語別に解説します。

C++ プログラム例（ABC275B）

整数の大きさと剰余の性質

C++ の整数は、表現できる範囲の大きさに上限を持ちます。以下は、AtCoder 環境の範囲です。整数の大きさについては、この記事でも解説しています。

• int が表現できる範囲　約 -2 × 10⁹ ～ 約 2 × 10⁹
• unsigned int が表現できる範囲　0 ～ 約 4 × 10⁹
• long long int が表現できる範囲　約 -9 × 10¹⁸ ～ 約 9 × 10¹⁸
• unsigned long long int が表現できる範囲　0 ～ 約 1.8 × 10¹⁹

問題にある制約

$$0 \leqq A, B, C, D, E, F \leqq 10^{18}$$

を考慮すると、先に 998244353（< 10⁹）で剰余を求めておく必要があります。そのまま計算すると、値により A × B だけでもオーバーフローします。

また、剰余については、以下が成立します。ここで $N \bmod M$ は、$N$ を $M$ で割った余りを表します。

• $A \bmod M \pm B \bmod M = (A \pm B) \bmod M$
• $A \bmod M \times B \bmod M = (A \times B) \bmod M$

この性質を使って、演算毎に剰余を求めていきます。これによりオーバーフローを避けることができます。

プログラム解答例

28行目の引き算は、正の値となるように 998244353 を加えて剰余を求めています。$A \times B \times C \geqq D \times E \times F$ は、$(A \times B \times C) \bmod M \geqq (D \times E \times F) \bmod M$ を意味しないため注意してください。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;

#define MOD 998244353

int main()
{
	ull a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;

	a %= MOD;
	b %= MOD;
	c %= MOD;
	d %= MOD;
	e %= MOD;
	f %= MOD;

	ull result = a;
	result = result * b % MOD;
	result = result * c % MOD;

	ull temp = d;
	temp = temp * e % MOD;
	temp = temp * f % MOD;

	result = (result + MOD - temp)% MOD;

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC275B）

Python の整数は上限がありません。この問題に限ると、以下のようにそのまま求められていることを書くだけです。

"""AtCoder Beginner Contest 275 B"""
a, b, c, d, e, f = map(int, input().split())
print(((a * b * c) - (d * e * f)) % 998244353)

演算毎に桁数が増えていくと計算時間が長くなる場合があります。この記事に実測例があります。そのような場合は、剰余を求めながら、桁数を抑えて演算します。

こちらも「AC」と判定されました。

最後に

採用するプログラミング言語によって、書く手間が大きく異なる問題でした。Python は、競技プログラミングにおいて、性能面で苦しい場合がある一方、表現は簡単に書ける場合が多いです。

引き続き ABC の問題を紹介していきます。