プロコン初心者日記

解いたプロコンの問題を保存しておくためのブログ

【yukicoder】No.3 ビットすごろく

yukicoderさんの問題

http://yukicoder.me/problems/no/3

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方***

・実装***

・面白さ***

以下にヒントがあります.

ヒント

幅優先全探索の問題.

コード

#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を使えば良い?
//----> __builtin_popcountめちゃ便利だった
//各マスに到達できる最小の回数を設定(初期値はINF)
//移動した時に最小値を更新できたらqueueに保存(1~N以外はcontinue)
//queueから一個取り出して次のマスを考える
//queueが空になったら終わり

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

    int bit1[N+1];
    //マスごとの2進数にした時の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;
}

コメント

2進数にした時の1の数を求める方法どうやるか迷ってたけど
__builtin_popcountめちゃ便利だった.
bitset使ってもできるようです
1の数が求められたらあとは幅優先全探索すればOK