この前のコンテストのD問題の解説を書く　第1回

・全編書き終わったらまとめて1記事にします。
・あっとこで言う灰色～茶色を対象に書きます。（ABCのABは解けるけどCが解けない人とか）
・言語はC++です（C++11機能まで使います）

問題の解説

popcount(n)をnを2進表記したときの'1'の個数とします。
例えば、popcount(3)＝2、popcount(7)＝3、popcount(0)＝0です。

3は2進数で「11」なので2、7は「111」なので3、0は「0」なので0ですね。（2進表記の説明は省略）

愚直に解いてみよう

まずは、制約とかは（できるだけ）無視して問題文を実装してみます。入力例１がAC出来る事が目標です。

入力は整数NとXが与えられますが、いきなり問題です。N≦2×10^5なので、Xは2進数で最大200000桁になります。64bitのlong long型に入る最大でも64桁になる（10進だと18桁くらい）なので、Xはintとかlong longとかでは受けられないです。ですが、最初に書いたとおり制約は気にせずに取り合えず進みます。取り合えず、文字列型（std::string）として受けておきます。
int型で受けない理由は、そのまま受けると2進の「011」（＝10進で3）ではなく、10進で「11」として受け取ってしまうためです。

入力だけだとこんな感じになります。

int main()
{
    int N;
    std::cin >> N;
    std::string X;
    std::cin >> X;
}

次は、関数f(n)を実装します。整数型の引数nを取り、操作回数を同じく整数型で戻します。型がsignだったりunsignedだったりしますが、説明の本筋ではないのであまり気にしないでください。（本当は色々よくないです）

unsigned long f(unsigned long n)
{
    int count = 0;
    while(n != 0){
        // nをpopcount(n)で割ったあまりに置き換える
        n = n % popcount(n);
        // 操作回数をカウント
        count++;
    }
    // nが0になるまでの操作回数を返す
    return count;
}

こんな感じです。これだけだと動かないので、popcount(n)を実装します。
引数は同じく整数としますが、「nを2進表記したときの'1'の数」を計算する必要があります。ここで、C++のビット配列（std::bitset）を使います。bitsetは、整数をビット配列の状態で表現する事ができます。今回は、count()関数を使います。
使い方は以下のリファレンスが分かり易いです（自分もしっかり使ったのは今回が初めてですが…）。bitsetのサイズは入力例１に合わせて3桁としましましたが、4桁以上の入力の場合は変える必要があります。
bitset - cpprefjp C++日本語リファレンス

int popcount(unsigned long n)
{
    std::bitset<3> bs(n);
    int count = bs.count();
    return count;
}

以上で、関数f(n)は実装できました。
入力Xを文字列で受けていたので、関数f(n)に渡すために整数に変換します。また、問題文にあるようにX自体をf(n)に渡すのではなく、「Xの上からi桁目のビットを反転した整数Xi」を渡します。やり方は色々ありますが、この場合も前述のbitsetを使うと簡単です。flip()はそのビットを反転させる（現在0なら1に、現在1なら0に変換する）操作、to_ulong()はビット配列をunsigned long型の整数に変換する操作です。

    std::string X;
    std::cin >> X;

    for(int i=N-1; i>=0; i--){
        std::bitset<3> bs(X);
        bs[i].flip();
        f(bs.to_ulong());
    }

これで実装は揃いました！思ったより長くなってしまいました。まとめると以下のようになります。

#include <iostream>
#include <string>
#include <bitset>

int popcount(unsigned long n)
{
    std::bitset<3> bs(n);
    int count = bs.count();
    return count;
}
    
unsigned long f(unsigned long n)
{
    int count = 0;
    while(n != 0){
        // nをpopcount(n)で割ったあまりに置き換える
        n = n % popcount(n);
        // 操作回数をカウント
        count++;
    }
    // nが0になるまでの操作回数を返す
    return count;
}

int main()
{
    int N;
    std::cin >> N;
    std::string X;
    std::cin >> X;

    for(int i=N-1; i>=0; i--){
        std::bitset<3> bs(X);
        bs[i].flip();
        unsigned long result = f(bs.to_ulong());
        
        std::cout << result << std::endl;
    }
}

出力

2
1
1

ちゃんと出力例１と同じ結果になりました。これで例１はAC出来ます。（提出してみてください）
第２回に続きます。

編集後記

ちゃんとした記事を書くのに慣れてないので、思ったより時間が掛かってしまった。
今週中に終わるのか…

NF

地方で働くプログラマ

この前のコンテストのD問題の解説を書く　第1回

目次

問題の解説

愚直に解いてみよう

編集後記