AtCoder

ABC357 D問題(88888888)を解く

AtCoder_ABC357_D

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 の問題を紹介していきます。

COMMENT

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

CAPTCHA