結果

問題 No.3 ビットすごろく
ユーザー @abcde@abcde
提出日時 2019-03-02 21:38:09
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,759 bytes
コンパイル時間 1,643 ms
コンパイル使用メモリ 167,964 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-23 13:01:23
合計ジャッジ時間 2,729 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 3 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 3 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 4 ms
6,944 KB
testcase_15 AC 5 ms
6,940 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 2 ms
6,944 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 1 ms
6,944 KB
testcase_22 AC 5 ms
6,940 KB
testcase_23 AC 5 ms
6,940 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 1 ms
6,940 KB
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

map<int, int> route;

// ビットを数える・探すアルゴリズム.
// 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;
}

// 経路情報更新.
// @param bef: 前回地点.
// @param dep: 経路の深さ.
// @param cur: 現在地点.
// @param limit: 経路の上限.
// @return: 特に無し.
void update(int bef, int dep, int cur, int limit){

    // 1. 現在地点が, 到達可能な経路から, はみ出していたら終了.
    if(cur > limit) return;
    if(cur < 1)     return;
    
    // 2. 経路長が, limit の 2倍を超えていたら終了.
    if(dep > limit * 2) return;
    
    // 3. すでに経路情報が更新されていたら終了.
    if(route[cur] > 0) return;
    
    // 4. 現在地点の経路情報を更新.
    if(cur > bef && route[cur] == 0) route[cur] = dep;

    // 5. 現在地点 cur の 1のビット数をカウント.
    int bit = countBits(cur);
    // cout << "cur= " << cur << " dep=" << dep << " bit=" << bit << " limit=" << limit << endl;
    
    // 6. 終了確認.
    if(cur == limit) return;
    
    // 7. 次の経路情報へ.
    update(cur, dep + 1, cur + bit, limit);
    update(cur, dep + 1, cur - bit, limit);

}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    
    // 2. N以下の数について, 経路を確認していく.
    route[1] = 0;
    update(1, 1, 1, N);
    
    // 3. 後処理.
    int ans = -1;
    if(route.count(N) > 0) ans = route[N];
    cout << ans << endl;
    return 0;
    
}
0