Yukicoder003 ビットすごろく

問題概要

$N$($N\leqq10^4$)が与えられます。 この$N$を2進数表現で表したとき、1が現れている数だけ、前に進むか後ろに進むことができる。 1からNに到達できるか判定し、もし到達できるなら、最小の移動回数を求めよ。

yukicoder003

解法

$Queue$に突っ込んで幅優先探索をすればOK

今回は大丈夫だけど、builtin_popcount()は正数しか受け付けていないので注意。

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    using PII = pair<int, int>;   using PLL = pair<LL, LL>;
    
    const int INF = 1e9;  
    
    
    LL N;
    
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N;
    
        VI dist(N + 1, INF);
        queue<PII>q;
        dist[1] = 1;
        q.push(PII(1, 1));
    
        while (!q.empty()) {
            int now = q.front().first;
            int ti = q.front().second;
            q.pop();
            if (now == N) {
                ans = ti;
                break;
            }
            int ad = __builtin_popcount(now);
            if (now - ad > 0 && dist[now - ad] > ti + 1) {
                q.push(PII(now - ad, ti + 1));
                dist[now - ad] = ti + 1;
            }
    
            if (now + ad <= N && dist[now + ad] > ti + 1) {
                q.push(PII(now + ad, ti + 1));
                dist[now + ad] = ti + 1;
            }
        }
        if (ans == 0)ans = -1;
        cout << ans << "\n";
    
        return 0;
    }