AtCoder

ABC298 D問題(Writing a Numeral)を解く

AtCoder_ABC298_D

AtCoder が提供しているABC(AtCoder Beginner Contest)298 のD問題をC++とPythonで解いてみました。ABC298は、2023年4月15日21:00に実施されました。

この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。

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

D問題 Writing a Numeral(Difficulty : 943)

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

ABC298 D問題 Writing a Numeral

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 に挑戦して、解説記事を書いていくつもりです。

COMMENT

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

CAPTCHA