結果

問題 No.3 ビットすごろく
コンテスト
ユーザー ser
提出日時 2017-08-17 00:18:38
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 998 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 443 ms
コンパイル使用メモリ 79,396 KB
最終ジャッジ日時 2026-03-22 05:33:29
合計ジャッジ時間 762 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:10:15: error: 'uint32_t' was not declared in this scope
   10 | int count_bit(uint32_t n) {
      |               ^~~~~~~~
main.cpp:7:1: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    6 | #include <queue>
  +++ |+#include <cstdint>
    7 | 
main.cpp: In function 'int main()':
main.cpp:33:27: error: 'count_bit' cannot be used as a function
   33 |         int bc = count_bit(n);
      |                  ~~~~~~~~~^~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <limits>
#include <queue>

using namespace std;

int count_bit(uint32_t n) {
    int c = 0;
    while(n) {
        if(n&0x01) c++;
        n >>= 1;
    }
    return c;
}

int main() {
    int first_n;
    scanf("%d", &first_n);

    vector<int> costs(first_n+1, numeric_limits<int>::max());
    costs[1] = 1;

    queue<int> q;
    q.push(1);

    while(!q.empty()) {
        int n = q.front();
        q.pop();

        int bc = count_bit(n);

        if(n + bc == first_n) {
            costs[n+bc] = costs[n] + 1;
            break;
        }

        if(n + bc < first_n && costs[n] + 1 < costs[n+bc]) {
            costs[n+bc] = costs[n] + 1;
            q.push(n+bc);
        }

        if(n - bc >= 1 && costs[n] + 1 < costs[n-bc]) {
            costs[n-bc] = costs[n] + 1;
            q.push(n-bc);
        }
    }

    printf("%d\n", costs[first_n]==numeric_limits<int>::max() ? -1 : costs[first_n]);
}
0