結果

問題 No.3 ビットすごろく
コンテスト
ユーザー sima.tetteke
提出日時 2019-10-12 18:09:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,479 bytes
コンパイル時間 1,724 ms
コンパイル使用メモリ 169,716 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 09:31:48
合計ジャッジ時間 2,582 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:11:10: warning: overflow in conversion from ‘float’ to ‘ll’ {aka ‘long long int’} changes value from ‘+Inff’ to ‘9223372036854775807’ [-Woverflow]
   11 | 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