AtCoder が提供しているABC（AtCoder Beginner Contest）336 のB問題をC++とPythonで解いてみました。ABC336は、2024年1月14日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 CTZ（Difficulty : 27）
問題はリンク先をご覧ください。
2進数表現したときの末尾の連続する0の個数を出力します。AtCoder Problems による Difficulty は 27 でした。
解答案
問題名の CTZ は、Count Trailing Zeros でしょうか。2つの考え方を紹介します。
C++ プログラム例（ABC336B）
一番小さなビットを取り出してゼロであるならば、読み込んだ $n$ を2で割っていきます。制約から $n$ は、0ではないため、いつかループを抜けます。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int result = 0;
while ((n & 1) == 0) {
++result;
n /= 2;
}
cout << result << endl;
return 0;
}次のC問題でも使えるK進数変換の自作関数を使ったプログラムを示します。
関数 Kfrom10 の仕様
- 整数 n と基数 k を与える。
- 整数 n を k 進数表記した文字列を返す。
Kfrom10 の返す文字列を調べて解答するプログラムは、以下となります。
#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;
string s = Kfrom10(n, 2);
int result = 0;
for (int i = s.length() - 1; i >= 0; --i) {
if (s[i] == '0') {
++result;
} else {
break;
}
}
cout << result << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC336B）
C++の最初のプログラムを移植します。以下となります。
"""AtCoder Beginner Contest 336 B"""
n = int(input())
result = 0
while (n & 1) == 0:
result += 1
n //= 2
print(result)2番目のプログラムも移植しました。以下となります。
"""AtCoder Beginner Contest 336 B"""
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())
s = Kfrom10(n, 2)
result = 0
for i in range(1, n + 1):
if s[-i] == '0':
result += 1
else:
break
print(result)こちらも「AC」と判定されました。
最後に
コンテストでは、手持ちの自作関数があったためC++の2番目のプログラムを提出しました。結果的に記事で最初に紹介したプログラムの方がすっきりと書けています。コンテスト中は、手の内化できている道具で解答して時間を稼いだつもりです。
引き続き ABC の問題を紹介していきます。
