結果

問題 No.3 ビットすごろく
ユーザー nenuonnenuon
提出日時 2017-02-27 23:04:15
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,952 bytes
コンパイル時間 865 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 08:26:48
合計ジャッジ時間 1,874 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//方針
//2進数にした時の1の個数はbitsetか1<<iを使えば良い?
//各マスに到達できる最小の回数を設定（初期値はINF）
//移動した時に最小値を更新できたらqueueに保存(1~N以外はcontinue)
//queueから一個取り出して次のマスを考える
//Nにたどり着く前にqueueが空になったら終わり

int main(){
    int N;
    cin >> N;

    int bit1[N+1];
    FOR(i, 0, N+1){
        bit1[i] = __builtin_popcount(i);
    }
    //quに次に始点となるマス番号を保存
    queue<int> qu;
    qu.push(1);

    //マスまで行くための最小値初期はINF
    int d[N+1];
    int INF = 99999999;
    fill(d, d+N+1, INF);
    d[1] = 0;

    while(!qu.empty()){
        //今見ている場所
        int now_x = qu.front();
        qu.pop();

        //Nに着いてたら次は調べない
        if(now_x == N) continue;

        //次に見る場所の候補
        int next_x1 = now_x + bit1[now_x];
        int next_x2 = now_x - bit1[now_x];

        //次見る場所が1~Nの中にあるかどうか
        if(next_x1 >= 1 && next_x1 <= N){
            //短い経路だったら次も調べる
            if(d[next_x1] > d[now_x] + 1){
                qu.push(next_x1);
                d[next_x1] = d[now_x] + 1;
            }
        }
        if(next_x2 >= 1 && next_x2 <= N){
            if(d[next_x2] > d[now_x] + 1){
                qu.push(next_x2);
                d[next_x2] = d[now_x] + 1;
            }
        }
    }
    cout << (d[N]==INF ? -1 : d[N]+1) << endl;
  }
0