ABC357 D問題（88888888）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）357 D問題をC++とPythonで解いてみました。ABC357は、2024年6月8日21:00に実施されました。

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

D問題 88888888（Difficulty : 970）

問題の詳細は、リンク先をご覧ください。

ABC357 D問題 88888888

等比数列の和を求めることに帰着します。AtCoder Problems による Difficulty は 970 でした。

解答案

入力例1の場合を分析します。3を3個つなげた333は、以下と考えることができます。

$$333 = 3 \times (1 + 10^1 + 10^2)$$

初項 $3$、公比 $10$ の等比数列の第 $1$ 項から第 $3$ 項までの和になっています。

与えられた $N$ に対して、$N$ を10進数で表現した桁数を $k$ とします。この場合、初項 $N$、公比 $10^k$ の等比数列の第 $1$ 項から第 $N$ までの和になります。

高校数学（数学Bで履修します）の復習となりますが、この等比数列の和は、以下となります。

$$N \times \frac{1 \;-\; (10^k)^n}{1 \;-\; 10^k}$$

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

$N$ の上限は $10^{18}$ と非常に大きいですが、$O(1)$ で解を求めることができます。998244353 で割った余りを求めるために ACL の modint を使います。このため、全体をすっきりと書くことができました。

プログラムを補足します。

• 与えられた $N$ の桁数 $k$ を求めます（14ー19行目）。
• 変数 t を $10^k$ とします（21行目）。
• 等比数列の和の公式を適用します（22行目）。

以下が、C++プログラムとなります。

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

typedef long long int ll;
typedef modint998244353 mint;

int main()
{
	ll n;
	cin >> n;

	ll k = 0;
	ll tn = n;
	while (tn > 0) {
		++k;
		tn /= 10;
	}

	mint t = ((mint)10).pow(k);
	mint result = (mint)n * (t.pow(n) - (mint)1) / (t - (mint)1);

	cout << result.val() << endl;

	return 0;
}

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

Python プログラム例（ABC357D）

Python 版も基本的な考え方は同じです。組込み関数 pow で mod 付きの累乗を求めることができます（12、13行目）。以下となります。

"""AtCoder Beginner Contest 357 D"""
MOD = 998244353
n = int(input())

k = 0
tn = n
while tn > 0:
    k += 1
    tn //= 10

t = (10 ** k) % MOD
inv = pow(t - 1, MOD - 2, MOD)
result = n * (pow(t, n, MOD) - 1) * inv
result %= MOD

print(result)

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

最後に

等差数列と等比数列の知識を使う問題は、ときどき出題される気がします。

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