結果

問題 No.3 ビットすごろく
コンテスト
ユーザー maine_honzuki
提出日時 2020-05-03 12:32:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 805 bytes
コンパイル時間 1,605 ms
コンパイル使用メモリ 173,304 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 09:47:20
合計ジャッジ時間 2,504 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    int bit_pop[10010] = {};
    for (int i = 1; i <= N; ++i) {
        bit_pop[i] = bitset<20>(i).count();
    }

    int dp[10010] = {};
    for (int i = 1; i <= N; i++)
        dp[i] = 11111;
    dp[1] = 1;
    queue<int> que;
    que.push(1);
    while (!que.empty()) {
        int now = que.front();
        que.pop();
        int nxt;
        nxt = now - bit_pop[now];
        if (nxt >= 1 && dp[nxt] == 11111) {
            dp[nxt] = dp[now] + 1;
            que.push(nxt);
        }
        nxt = now + bit_pop[now];
        if (nxt <= N && dp[nxt] == 11111) {
            dp[nxt] = dp[now] + 1;
            que.push(nxt);
        }
    }
    if (dp[N] == 11111)
        dp[N] = -1;
    cout << dp[N] << endl;
}
0