結果

問題 No.3 ビットすごろく
ユーザー sima.tettekesima.tetteke
提出日時 2019-10-12 18:09:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,479 bytes
コンパイル時間 1,351 ms
コンパイル使用メモリ 155,416 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-09-14 01:28:58
合計ジャッジ時間 2,574 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 3 ms
4,380 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 4 ms
4,376 KB
testcase_16 AC 4 ms
4,380 KB
testcase_17 AC 3 ms
4,384 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 3 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 3 ms
4,376 KB
testcase_23 AC 4 ms
4,376 KB
testcase_24 AC 3 ms
4,380 KB
testcase_25 AC 4 ms
4,388 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 4 ms
4,380 KB
testcase_29 AC 3 ms
4,380 KB
testcase_30 AC 1 ms
4,380 KB
testcase_31 AC 2 ms
4,376 KB
testcase_32 AC 3 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:11:10: warning: overflow in conversion from ‘float’ to ‘ll’ {aka ‘long long int’} changes value from ‘+Inff’ to ‘9223372036854775807’ [-Woverflow]
 ll ans = INFINITY;
          ^~~~~~~~

ソースコード

diff # 

#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;

ll ans = INFINITY;
ll N;

vector<ll > bfs(vector<vector<ll > > G, ll start){
    start;
    //距離を初期化
    vector<ll > dist(G.size(), -1);
    queue<ll > que;

    //始点start 初期化
    dist[start] = 0;
    que.push(start);

    while(!que.empty()){
        ll from = que.front();
        que.pop();

        for(ll i = 0; i < G[from].size(); i++){
            ll to = G[from][i];
            //すでに探査済み
            if(dist[to] != -1) continue;

            dist[to] = dist[from] + 1;
            que.push(to);
        }
    }

    return dist;

}

int main(){


    cin >> N;

    vector<vector<ll > > G;
    G.assign(N + 1, vector<ll >());
    
    //0から開始マス1への移動
    G[0].push_back(1);

    for(ll i = 1; i <= N; i++){
        ll bit_count = __builtin_popcount(i);
        //cout << i-1 + bit_count << " " << i-1 - bit_count << endl;
        if(i + bit_count <= N){
            G[i].push_back(i + bit_count);
            //G[i-1 + bit_count].push_back(i-1);
            //cout << 0 << endl;
        } 
        if(i - bit_count > 0){
            G[i].push_back(i - bit_count);
           //G[i-1 - bit_count].push_back(i-1);
            
        }
    }

    vector<ll > dist = bfs(G, 0);

    cout << dist[N] << endl;

}
0