AtCoder が提供しているABC（AtCoder Beginner Contest）298 のD問題をC++とPythonで解いてみました。ABC298は、2023年4月15日21:00に実施されました。
この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Writing a Numeral（Difficulty : 943）
問題はリンク先をご覧ください。
Deque を使って解きました。AtCoder Problems による Difficulty は 943 でした。
解答案
3種類のクエリを処理する必要があります。
格納されている数字の観点でクエリを整理します。ただし結果は 998244353 で割った余りを出力します。
- クエリ1: 格納されている数字を10倍して x（1から9）を加える。
- クエリ2: 格納されている一番上位の桁を削除する。
- クエリ3: 格納されている数字を出力する。
クエリ1では、数字の末尾を加えて、クエリ2では、数字の先頭の値を削除します。そのため両方向の操作ができるコンテナを使う必要があります。
クエリ2では、例えば、1234567890 に対して、1000000000 を引くことになります。クエリの回数の上限が、6 × 105 となるため、対象となる数字は非常に大きくなります。
C++ プログラム例（ABC298D）
C++では、両方向の操作ができる deque を採用しました。deque については、この記事で紹介しています。push_back で末尾に追加して、front で値を読み出し、pop_front で先頭の値を削除します。
クエリ2では、modを取りながら10のべき乗を計算する必要があります。このために関数 power を用意しました（8-17行目）。途中、慎重に mod を計算しているため、コードが少し煩雑になっています（39、40行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
#define MOD 998244353
int power(int n, int p, int mod) {
if (p == 0) {
return 1;
}
if (p % 2 == 0) {
long long int t = power(n, p / 2, mod);
return (int)(t * t % mod);
}
return (int)(((long long int)n * power(n, p - 1, mod))% mod);
}
int main()
{
int q;
cin >> q;
deque<int> s;
s.push_back(1);
ull result = 1;
for (int i = 0; i < q; ++i) {
int command;
cin >> command;
if (command == 1) {
int x;
cin >> x;
s.push_back(x);
result = (result * 10 + x)% MOD;
} else if (command == 2) {
ull top = s.front();
s.pop_front();
result = result - (top * power(10, s.size(), MOD)% MOD);
result = (result + MOD)% MOD;
} else if (command == 3) {
cout << result % MOD << endl;
}
}
return 0;
}AtCoder Library（ACL）を使ったプログラムも紹介します。ACL は、AtCoder のコンテストで使えるライブラリです。全体の説明は、こちらにあります。
ACL が提供している機能のひとつである modint を使うことによって、自動で mod を計算することができます。AtCoder でよく使われる 998244353 や 1000000007 にも対応しています。
modint に関係しているコードの背景色を変更しました。これらのコードを読めば、ライブラリの使い方が分かると思います。ライブラリの効果でコードがすっきりと書けています。
#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 q;
cin >> q;
deque<int> s;
s.push_back(1);
mint result = 1;
for (int i = 0; i < q; ++i) {
int command;
cin >> command;
if (command == 1) {
int x;
cin >> x;
s.push_back(x);
result = result * 10 + x;
} else if (command == 2) {
mint top = s.front();
s.pop_front();
result = result - top * ((mint)10).pow(s.size());
} else if (command == 3) {
cout << result.val() << endl;
}
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC298D）
Python も deque を使いました。append で末尾に追加して、popleft で先頭の値を取り出して削除します（14、17行目）。
Python では、mod 付きの階乗は、pow で求めることができます（18行目）。mod 無しの階乗は、演算子 ** で計算できます。
"""AtCoder Beginner Contest 298 D"""
from collections import deque
MOD = 998244353
q = int(input())
s = deque()
s.append(1)
result = 1
for i in range(q):
query = list(map(int, input().split()))
if query[0] == 1:
s.append(query[1])
result = (result * 10 + query[1]) % MOD
elif query[0] == 2:
top = s.popleft()
result = result - (top * pow(10, len(s), MOD)) % MOD
result = (result + MOD) % MOD
elif query[0] == 3:
print(result % MOD)こちらも「AC」と判定されました。
最後に
今回は、B問題とC問題で問題を読み間違えて時間が過ぎていました。このD問題は、コンテスト中に解くことができませんでした。解説することによって学べました。
AtCoder は、1年ほど中断して、ABC269からブログで解説記事を書いていました。2回ほど参加できませんでしたが、後で解いて解説記事は続けました。解説記事を書くことによって、理解を深めることができたと考えています。
引き続き ABC の問題を紹介していきます。
