読者です 読者をやめる 読者になる 読者になる

C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

No.3 ビットすごろく|yukicoder|幅優先探索(BFS)

No.3 ビットすごろく - yukicoder を解きました。

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const int INF = numeric_limits<int>::max();
int f( int N )
{
    int count{};
    while( N > 0 )
    {
        if( N % 2 == 1 ) count++;
        N /= 2;
    }
    return count;
}
int main()
{
    int N;
    cin >> N;
    
    queue<int> q;
    q.push(1);//初期状態: 頂点 1にする
    vector<int> dist( N + 1, INF );//最大値で埋める <-N+1!!!!!!!
    dist[1] = 1;//初期状態:始点からの距離1を入れる
    
    while( !q.empty() )//queueが空でない場合継続
    {
        int now = q.front();//now == 現在地 //queueから取り出す
        q.pop();//削除
        int bit = f( now );//現在のqueueのbit[1]数取得
        
        //distances[v] == INF が未訪問,到達不可能なことと同値 <-!!!!!!!
        if( now - bit > 0 && dist[ now - bit ] == INF )//now-bit数が0以上,未訪問の場合
        {
            dist[ now - bit ] = dist[ now ] + 1;//点の距離をnowから+1の距離で確定する
            q.emplace( now - bit );//次の位置をqueueに入れる
        }
        if( now + bit <= N && dist[ now + bit ] == INF )//now+bit数がN以下,未訪問の場合
        {
            dist[ now + bit ] = dist[ now ] + 1;//点の距離をnowから+1の距離で確定する
            q.emplace( now + bit );//次の位置をqueueに入れる
        }
    }
    //dist[N]には始点からの最短距離が入っている
    cout << ( dist[ N ] < INF ? dist[ N ] : -1 ) << endl;
    return 0;
}

初めて幅優先探索(BSF)というアルゴリズムを使って解ける問題を解きました。

題意はNが与えられるので、1からNまでのマスの数字を2進数に変換、bitの立っている数だけ前後に進む事が出来るので、Nぴったりでゴールするというサイコロゲームの最小移動回数を求めるもの。
※1未満とN+1以上のマスには移動することは出来ない

1からNまでの数字を2進数に変換してbit 1 をcountする所だけ別に関数で持ちました。
10進数から2進数に変換するのは商が0になるまで2で割って余りが1になる時をcountするだけなのですが...
__builtin_popcount という便利なgccビルトイン関数というのを知り得ました。
__builtin_popcount はbitが立っている数をそのまま返してくれます*1
int bit = __builtin_popcount( 3 ); で 2 が返ってきます。(3は二進数で011)
なので__builtin_popcountを使うと別関数で持った部分が全部不要となって1行で済みます!(便利)
便利なのですが、便利すぎなので一度実装して挙動を確かめるに留まりました。

そしてBFSの部分はコードにコメントを全行入れているのでそのままです。
距離と訪問済みフラグを1つの配列にまとめて持つ事でコードが簡潔になる様です。

AC後何日もコードの処理が腑に落ちず考え込んでいましたが、ノートにコードの動きをそのまま処理順に書いて追ってみたら理解できました...。

【今回BFSの理解、コードを書く上で参考にしたもの】
・TLE本
・蟻本
・プログラミングの宝箱 アルゴリズムとデータ構造 第2版
yukicoder 3/4/5 - 競技プログラミングをするんだよ
yukicoder 0003 ビットすごろく - みさわめも
・この問題にC++11/14で提出されてた任意のプロのACコード
・グラフの図(N=5の場合の図)
f:id:chiwawa_star:20160814022431j:plain:w400

/*追記*/
C++で2進数のbit 1を数える方法、std::bitset がある事を教えて頂きました。
こっちの方が覚えやすいかも....。
参照:C++ でハミング重みを求める その2 - Secret Garden(Instrumental)