AtCoder が提供しているABC（AtCoder Beginner Contest）372 B問題をC++とPythonで解いてみました。ABC372は、2024年9月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 3^A（Difficulty : 131）
問題の詳細は、リンク先をご覧ください。
与えられた整数を3進数で表現します。AtCoder Problems による Difficulty は 131 でした。
解答案
入力例2の100を次の式で表現します。
$$100 = 81 + 18 + 1 = 1 \times 3^4 + 2 \times 3^2 + 1 \times 3^0$$
$$ = 1 \times 3^4 + 1 \times 3^2 + 1 \times 3^2 + 1 \times 3^0$$
上記の結果から出力は、”4 2 2 0″ となります。与えられた整数を3進数で表現すればよいことが分かります。
C++ プログラム例（ABC372B）
3進数は下の桁から求めていきます（10ー19行目）。変数 t の値が3進数表現の各桁の値となります。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m;
cin >> m;
vector<int> result;
for (int i = 0; i <= 10; ++i) {
int t = m % 3;
m /= 3;
if (t == 1) {
result.push_back(i);
} else if (t == 2) {
result.push_back(i);
result.push_back(i);
}
}
cout << result.size() << endl;
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << " \n"[i == result.size() - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC372B）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 372 B"""
m = int(input())
result = []
for i in range(11):
t = m % 3
m //= 3
if t == 1:
result.append(i)
elif t == 2:
result.append(i)
result.append(i)
print(len(result))
print(*result)こちらも「AC」と判定されました。
最後に
3進数に変換するということに気付けば解きやすい問題でした。
引き続き ABC の問題を紹介していきます。
