AtCoder が提供しているABC（AtCoder Beginner Contest）321 のC問題をC++とPythonで解いてみました。ABC321は、2023年9月23日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 321-like Searcher（Difficulty : 591）
問題はリンク先をご覧ください。
321-like Number の構造に気が付けば解くことができます。AtCoder Problems による Difficulty は 591 でした。
解答案
この問題で与えられる $K$ について、$1 \leqq K$ という制約が示されています。上限の制約がありません。一方、「321-like Number は $K$ 個以上存在する」という制約があります。
一番大きな 321-like Number は、10桁の 9876543210 であることが分かります。その次に大きな数は、9桁の 987654321 となります。また、9桁の数は、0 から 9 を抜いた 10 個しかないことが分かります。10桁の 321-like Number がある一方、それほどの個数が無いことが予想できます。
以下は公式解説を参考にしました。
321-like Number は、同じ数字を2個含むことはありません。
- 0 を含むか、含むかないかのどちらか。
- 1 を含むか、含むかないかのどちらか。
- …
- 9 を含むか、含むかないかのどちらか。
各数字の有無をbit全探索で考えます。また、0は対象となりません。このため、すべて2進数が0の組み合わせと、0だけある場合（0000000001）は、対象となりません。このため、321-like Number は、$2^{10} – 2 = 1022$ 個しかありません。
C++ プログラム例（ABC321C）
bit全探索を使います。前述の考察からループを2から開始します（12行目）。大きな数から取り出すため、次のループを9から0の順番で処理しています（14行目）。
bit全探索でビットがセットされている数字を大きな順に並べて、配列 result に格納します。最終的に result をソートして解答します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int k;
cin >> k;
vector<ll> result;
for (int i = 2; i < (1 << 10); ++i) {
ll no = 0;
for (int j = 9; j >= 0; --j) {
if ((i & (1 << j)) != 0) {
no = no * 10 + j;
}
}
result.push_back(no);
}
sort(result.begin(), result.end());
cout << result[k - 1] << endl;
return 0;
}優先度付きキューを使った別解
優先度付きキューを使ったプログラムも紹介します。
- 0 から 9 までの数字をキューに格納します（12ー14行目）。
- キューから取り出した数字の最大の桁の数字（tn）のひとつ大きな桁の数字（i）を設定してキューに格納します。
- 例1）0 を取り出したら、10、20、…、90 を格納する。
- 例2）10 を取り出したら、210、310、…、910 を格納する。
- 例3）910 を取り出したら、格納する数字はない。
- 例4）876543210 を取り出したら、9876543210 を格納する。
- ある桁（たとえば2桁）の数をすべて処理したら、次の桁（3桁）の数の処理をします。
- 321-like Number を小さい順に no で管理します。no = -1 としているのは、キューから取り出す 0 を 0 番目に、1 を 1 番目にするためです。
すでに考察したように、321-like Number は、1022個しかないため、このプログラムも十分に速く動作しました（C++20 で 6ms でした）。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int k;
cin >> k;
priority_queue<ll, vector<ll>, greater<ll>> que;
for (ll i = 0; i <= 9; ++i) {
que.push(i);
}
ll base = 10;
ll no = -1;
while (1) {
ll t = que.top();
while (t < base) {
que.pop();
++no;
if (no == k) {
cout << t << endl;
return 0;
}
ll tn = t / (base / 10);
for (ll i = tn + 1; i <= 9; ++i) {
que.push(i * base + t);
}
t = que.top();
}
base *= 10;
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC321C）
Python は、bit全探索のプログラムを移植しました。以下となります。
"""AtCoder Beginner Contest 321 C"""
k = int(input())
result = []
for i in range(2, 2**10):
no = 0
for j in range(9, -1, -1):
if (i & (1 << j)) != 0:
no = no * 10 + j
result.append(no)
result.sort()
print(result[k - 1])こちらも「AC」と判定されました。
最後に
この問題は、当初 DP を使って解こうとしていました。うまく書くことができず、優先度付きキューを使う方法を思いつきましたが、コンテスト中は時間が足りませんでした。
公式解説を参考にbit全探索のプログラムを書いた後に、キューを使うプログラムでもACを取ることができました。勉強になりました。
引き続き ABC の問題を紹介していきます。
