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