AtCoder が提供しているABC(AtCoder Beginner Contest)357 D問題をC++とPythonで解いてみました。ABC357は、2024年6月8日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 88888888(Difficulty : 970)
問題の詳細は、リンク先をご覧ください。
等比数列の和を求めることに帰着します。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 の問題を紹介していきます。