結果

問題 No.3 ビットすごろく
コンテスト
ユーザー @abcde
提出日時 2019-03-03 17:29:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,999 bytes
コンパイル時間 1,308 ms
コンパイル使用メモリ 164,008 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 09:14:59
合計ジャッジ時間 2,321 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

// 訪問済みか否かを設定.
bool isVisited[10001];
// 地点1からの経路数を保存.
int route[10001];

// ビットを数える・探すアルゴリズム.
// http://www.nminoru.jp/~nminoru/programming/bitcount.html
int countBits(int bits){
    int num;
    num = (bits >> 1) & 03333333333;
    num = bits - num - ((num >> 1) & 03333333333);
    num = ((num + (num >> 3)) & 0707070707) % 077;
    return num;
}

// 経路情報更新.
// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// @param vCur: 現在地点.
// @param vMax: 探索可能な頂点の最大値.
// @return: 特に無し.
void bfs(int vCur, int vMax){

    // 1. queue の 設定.
    queue<int> Q;
    Q.push(vCur);
    isVisited[vCur] = true; // 現在地点 vCur を 訪問済みに設定.
    
    // 2. queue が 空になるまで, 探索.
    while(!Q.empty()){
        
        // 2-1. Q から 取り出す.
        int u = Q.front();
        Q.pop();
        
        // 2-2. 探索地点 u の 1のビット数をカウント.
        int bit = countBits(u);
        // cout << "u=" << u << " route[" << u << "]=" << route[u] << " isVisited[" << u << "]=" << isVisited[u] << endl;
        
        // 2-3. 探索地点 u に, 接続している頂点について確認.
        // -> wiki の 疑似コード上 "for each v に接続している頂点 i do" を 読み替えしている.
        // ① +bit個 右(indexを増やす方向) の 頂点 vr に移動する場合.
        int vr = u + bit;
        if(vr <= vMax && route[vr] == -1 && isVisited[vr] == false){
            route[vr] = route[u] + 1;
            // cout << " vr=" << vr << " route[" << vr << "]=" << route[vr] << endl;
            isVisited[vr] = true;  // 訪問済みをマーク.
            Q.push(vr); // vr を Q に追加
        }
        // ② -bit個 左(indexを減らす方向) の 頂点 vl に移動する場合.
        int vl = u - bit;
        if(vl >= 0 && route[vl] == -1 && isVisited[vl] == false){
            route[vl] = route[u] + 1;
            // cout << " vl=" << vl << " route[" << vl << "]=" << route[vl] << endl;
            // isVisited[vl] = true;  // 訪問済みのマークは行わない.
            Q.push(vl); // vl を Q に追加
        }
    }

}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    
    // 2. 経路を確認していく.
    for(int i = 0; i < 10001; i++) route[i] = -1, isVisited[i] = false;
    // system_test2.txt の WA回避用？(N = 1 ならば, 経路数 0 を設定？？).
    // if(N > 1)  route[1] = 1;
    // if(N == 1) route[1] = 0;
    // -> 上記設定だと, AC に ならなかった.
    // system_test2.txt の WA回避用？(N = 1 に関わらず, 経路数 1 を設定？？).
    route[1] = 1;

    // N = 10000 -> 経路数: 1610 らしい.
    bfs(1, N);
    
    // 3. 後処理.
    int ans = route[N];
    cout << ans << endl;
    return 0;
    
}
0