ABC353 D問題（Another Sigma Problem）を解く

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

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

D問題 Another Sigma Problem（Difficulty : 844）

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

ABC353 D問題 Another Sigma Problem

要素の後ろから処理します。累積和も使います。AtCoder Problems による Difficulty は 844 でした。

解答案

C問題とは関数 $f$ が異なりますが、同じ式の結果を求めます。

入力例3の場合を振り返ります。

$j=5$ の列に注目します。下6桁の 100000（赤字）は、共通となります。その上位（青字）は、$A_1$ から $A_4$ までの和に $10^6$ を掛けたものに等しくなります。結果としては以下となります。

$$(\sum^{4}_{i=1} A_i) \times 10^6 + 100000\;(A_5) \times (5 – 1)$$

列4、列3、列2、列1も同じように求めることができます。上位となる青字の数字は、累積和として計算しておきます。

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

プログラムの補足です。

• 998244353 の剰余を求めるために ACL の modint を使います（2、4、7行目）。
• 準備として、配列の前から $N-1$ 個の和を求めておきます（17ー19行目）。
• 10のべき乗の値を準備しておきます（22ー26行目）。
• 後ろの要素から処理をしてきます。
  • 数字の桁数を文字列化して求めて（変数 k）、考察した式の結果を変数 result に加えます（30、31行目）。
  • 和（sum）の値から、1個前の値を引いて、次の演算に使います（32行目）。

以下が、C++プログラムです。

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

typedef unsigned long long int ull;
typedef modint998244353 mint;

int main()
{
	int n;
	cin >> n;
	vector<ull> a(n);
	mint sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (i != n - 1) {
			sum += a[i];
		}
	}

	vector<mint> p10(12);
	p10[0] = (mint)1;
	for (int i = 0; i < 11; ++i) {
		p10[i + 1] = p10[i] * 10;
	}

	mint result = 0;
	for (int i = n - 1; i > 0; --i) {
		int k = to_string(a[i]).length();
		result += p10[k] * sum + a[i] * i;
		sum -= a[i - 1];
	}

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

	return 0;
}

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

Python プログラム例（ABC353D）

基本的な考え方は同じです。以下となります。Python 版の方がすっきりと書けています。

"""AtCoder Beginner Contest 353 D"""
MOD = 998244353
n = int(input())
a = list(map(int, input().split()))
s = sum(a[:n - 1])

result = 0
for i in range(n - 1, 0, -1):
    result += 10 ** len(str(a[i])) * s + a[i] * i
    result %= MOD
    s -= a[i - 1]

print(result)

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

最後に

D問題ですが、すんなり解くことができました。当初は、緑Diffの問題が全く解けなかったので、うれしく感じます。

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