AtCoder が提供しているABC（AtCoder Beginner Contest）336 のC問題をC++とPythonで解いてみました。ABC336は、2024年1月14日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Even Digits（Difficulty : 343）
問題はリンク先をご覧ください。
5進数と考えると楽になります。AtCoder Problems による Difficulty は 343 でした。
解答案
制約が $1 \leqq N \leqq 10^{12}$ と大きいため、数字に含まれている桁が偶数だけか確認していては、間に合いません。
一方、登場する数字が、0、2、4、6、8 の5種類しかないため、5進数と考えると上手く行きます。
C++ プログラム例（ABC336C）
以下の関数を自作して持っていました。
関数 Kfrom10 の仕様（6ー18行目）
- 整数 n と基数 k を与える。
- 整数 n を k 進数表記した文字列を返す。
プログラム全体の補足をします。
- 数字0を1番目とするため、入力 $n$ から1を引いて処理します（24行目）。
- 5進数の数字を元の数字に戻す必要があります（30行目）。
0→0、1→2、2→4、3→6、4→8
以下が、最終的なC＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
string Kfrom10(ull n, int k) {
string result = "";
while (n > 0) {
result = (char)(n % k + '0') + result;
n /= k;
}
if (result == "") {
result = "0";
}
return result;
}
int main()
{
ull n;
cin >> n;
--n;
string s = Kfrom10(n, 5);
string result;
for (int i = 0; i < s.length(); ++i) {
result += (s[i] - '0') * 2 + '0';
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC336C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 336 C"""
def Kfrom10(n, k):
result = ""
while n > 0:
result = chr((n % k) + ord('0')) + result
n //= k
if result == "":
result = "0"
return result
n = int(input()) - 1
s = Kfrom10(n, 5)
result = ""
for _, ch in enumerate(s):
result += chr((ord(ch) - ord('0')) * 2 + ord('0'))
print(result)こちらも「AC」と判定されました。
最後に
コンテストでは、AからC問題のACを 9分17秒でもらうことができました。わたくしにとっては、非常に速かったです。自作ライブラリの整備は、速解きには有効であると感じました。
引き続き ABC の問題を紹介していきます。
