【AtCoder】ABC 336 B - CTZ | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 27

問題概要

正整数 について、 を2進数表示したときに末尾に連続する の個数の最大値を と定義する。正整数 に対して を出力せよ。

制約

• 

考察

問題文に従って を2進数に変換して文字列化し、末尾に連続する の個数を数えてしまおう。ここで、基数変換には以前実装したライブラリを使用している。詳しくはこちら。

yuulis.hatenablog.com

コード

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

// ======================================== //

// Arbitrary radix conversion
std::string radix_conversion(const std::string x, const int from, const int to)
{
    // Conversion table.
    // To be changed as appropriate.
    const std::string table = "0123456789abcdef";
    assert((2 <= from && from <= 16) && (2 <= to && to <= 16));

    unsigned long sum = 0;
    for (char c : x)
    {
        sum = sum * from + table.find(c);
    }

    std::string res = "";
    do
    {
        int mod = sum % to;
        res = table[mod] + res;
        sum /= to;
    } while (sum);

    return res;
}

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

    string x = radix_conversion(to_string(N), 10, 2);
    int cnt = 0, idx = x.size() - 1;
    while (x[idx] == '0')
    {
        cnt++;
        idx--;
    }

    cout << cnt << endl;
}

atcoder.jp

実装時間: 5分以内

C++ 標準ライブラリにstd::countr_zeroっていうやつがあるらしく、それがこの問題の元になっているようだ。