ABC333 C問題（Repunit Trio）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）333 のC問題をC++とPythonで解いてみました。ABC333は、2023年12月16日21:00に実施されました。

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

C問題 Repunit Trio（Difficulty : 258）

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

ABC333 C問題 Repunit Trio

入力例から上限が分かるため、3重ループで全探索します。AtCoder Problems による Difficulty は 258 でした。

解答案

重要なヒントが入力例3として提示されていました。

• 入力例3：333（制約の上限）
• 出力例3：112222222233

これから、12桁までのレピュニット（すべての桁の数字が1である整数）を考えればよいことが分かります。3重ループとなりますが、${12}^3=1728$ なので、十分に間に合います。

上限を計算する

3つのレピュニットの和は、足し算の性質から以下が分かります。出力例3も参考にしてください。

• 一番小さな桁は3になる。
• 大きい桁から1または2または3が続き、一度2がでたら、2か3しかでない。一度3がでたら、残りはすべて3となる。

出力例3について、1と2の切れ目と2と3の切れ目を×で表現すると以下のように表現できます。

11x22222222x3

一番小さな桁を除いた11桁に対して、切れ目2か所を選ぶ場合の数は、${}_{11+2}{C}_2$ 通りとなることが分かります。一般に一番小さな桁を除いた$n$桁に対して、和の結果としてあり得るのは、${}_{n+2}{C}_2$ 種類となります。以下計算しました。

$N$ の上限333に対して、12桁まで計算すればよいことが分かりました。

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

レピュニットを配列 ones に格納します。念のため13個格納しました（12ー17行目）。3重ループを使って、set コンテナ result に格納して、小さい方から n 番目の数字を出力します。

以下が、C＋＋プログラムとなります。

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

typedef long long int ll;
#define N 13

int main()
{
	int n;
	cin >> n;

	vector<ll> ones;
	ll num = 0;
	for (int i = 0; i < N; ++i) {
		num = num * 10LL + 1LL;
		ones.push_back(num);
	}

	set<ll> result;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = 0; k < N; ++k) {
				result.insert(ones[i] + ones[j] + ones[k]);
			}
		}
	}	

	int index = 1;
	for (auto e : result) {
		if (index == n) {
			cout << e << endl;
		}
		++index;
	}

	return 0;
}

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

Python プログラム例（ABC333C）

Python の set は、順序付きではないため、出力時にソートしています（17行目）。以下となります。

"""AtCoder Beginner Contest XXX Y"""
N = 13
n = int(input())

ones = []
num = 0
for i in range(N):
    num = num * 10 + 1
    ones.append(num)

result = set()
for i in range(N):
    for j in range(N):
        for k in range(N):
            result.add(ones[i] + ones[j] + ones[k])

print(sorted(result)[n - 1])

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

最後に

入力例が非常に大きなヒントとなりました。計算する上限を考えるのが難しいと出題側で判断したと思われます。わたしには助かりました。

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