AtCoder

ABC275 B問題(ABC-DEF)を解く

AtCoder_ABC275_B

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 でした。ABC B問題として、標準的な問題です。

解答案

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

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

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

C++ プログラム例(ABC275B)

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

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

  • int が表現できる範囲 約 -2 × 109 ~ 約 2 × 109
  • unsigned int が表現できる範囲 0 ~ 約 4 × 109
  • long long int が表現できる範囲 約 -9 × 1018 ~ 約 9 × 1018
  • unsigned long long int が表現できる範囲 0 ~ 約 1.8 × 1019

問題にある制約

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

を考慮すると、先に 998244353(< 109)で剰余を求めておく必要があります。そのまま計算すると、値により 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 は、競技プログラミングにおいて、性能面で苦しい場合がある一方、表現は簡単に書ける場合が多いです。

ABC275 について、引き続き、D問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA