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

競プロ記録

問題を解いた際に自分の復習用として使ってます

No.3 ビットすごろく

競技プログラミング

yukicoder No.3 ビットすごろくの解説

この問題はある数字Nが与えられ。1〜Nの区間での最小の移動回数を求めます。

位置の数字を2進数で表し「1」のbit数だけ前、後に移動することができます。

まずqueueとしてQを宣言します。Qにはその位置から移動できる場所を入れていきます。前に移動した場合と後に移動した場合の2通りを入れていきます。

そして移動した回数を保存していく配列dを宣言します。

また移動したか、していないかを保存する配列を宣言します。

移動したことがあるばい、前回に保存されている方が移動回数は少ないため更新する必要性はありません。この操作を移動できなくなる。つまりキューが空になるまで続けることで答えを導き出すことができます。

数字の「1」のビット数を数得る場合は__builtin_popcount 関数を使えば求めることができます。

以上解説でした。

以下ソースコードになります。

#include <iostream>
#include <queue>
using namespace std;
const int INF = 100000000;

int main(void){
    int n, i;
    int v[10005], d[10005]; //vは移動したかしていないかを判別する配列、dはiまでの最小移動回数を保存する配列
    cin >> n;
    for(int i=1;i<=n;i++){
        v[i] = 0;    //全て移動していないことにする。
    }
    for(int i=1;i<=n;i++){
        d[i] = INF;    //全て移動移動できないとしておく
    }
    
    queue<int> que;    //queは移動できる場所を格納する
    que.push(1);
    v[1] = 1;
    d[1] = 1;

    while(!que.empty()){
        int bit;
        i = que.front();
        que.pop();
        bit = __builtin_popcount(i);    //この関数は「1」のbit数を返してくれる
        if(i+bit >= 1 && i+bit <= n && v[i+bit] == 0){
            que.push(i+bit);
            v[i+bit] = 1;
            d[i+bit] = d[i] + 1;
        }
        if(i-bit >= 1 && i-bit <= n && v[i-bit] == 0){
            que.push(i-bit);
            v[i-bit] = 1;
            d[i-bit] = d[i] + 1;
        }
    }
    cout << (d[n] != INF ? d[n] : -1) << endl;
     return 0;
}