#78219 (C++11（廃止可能性あり）) No.262 面白くないビットすごろく

• 問題: No.262 面白くないビットすごろく
• ユーザー: Tatamo
• 提出日時: 2016-02-26 21:42:26
• 言語: C++11（廃止可能性あり） (gcc 13.3.0)
• 結果: AC
• 実行時間: 257 ms / 2,000 ms
• コード長: 2,469 bytes
• コンパイル時間: 495 ms
• コンパイル使用メモリ: 56,884 KB
• 実行使用メモリ: 339,368 KB
• 最終ジャッジ日時: 2024-09-22 14:02:52
• 合計ジャッジ時間: 1,614 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
other	AC * 4

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
inline unsigned long long popcount(unsigned long long x) { return __builtin_popcountll(x); }
#define BITS_MAX (40)
#define BITS_LOWER (20)
using namespace std;
typedef unsigned long long ull;
struct Point {
    ull need2overflow;
    ull next;
};
// problems/402
int main() {
    ull x;
    cin >> x;
    const ull n = x;
    int i = 0;
    ull tmp = n;
    while (true) {
        if (tmp >> 1 == 0) break;
        tmp = tmp >> 1;
        i++;
    }
    ull nbits = i;
    ull bits_upper = nbits >= BITS_LOWER ? nbits - BITS_LOWER : 1;
    bits_upper++; // 行き過ぎるために多少オーバーすることがあるので、一桁多く取る
    //Point P[BITS_MAX][1 << BITS_LOWER];
    Point** P = new Point*[bits_upper];
    for (int i = 0; i < bits_upper; i++) {
        P[i] = new Point[1 << BITS_LOWER];
        for (int ii = 0; ii < 1 << BITS_LOWER; ii++) {
            P[i][ii].need2overflow = 0;
        }
    }
    ull* bits_pc = new ull[1 << BITS_LOWER];
    for (int i = 0; i < 1 << BITS_LOWER; i++) {
        bits_pc[i] = popcount(i);
    }
    // 下BITS_LOWERビットについて調べる
    for (int i = 0; i < bits_upper; i++) {
        for (long long ii = (1 << BITS_LOWER) - 1; ii >= 0; ii--) {
            if (i == 0 && ii == 0) continue;
            ull bit = ii;
            ull max = (1 << BITS_LOWER);
            ull c = 0;
            while (true) {
                c++;
                bit += i + bits_pc[bit];
                if (bit >= max) {
                    bit -= max;
                    break;
                }
                if (P[i][bit].need2overflow > 0) { // DP
                    c += P[i][bit].need2overflow;
                    bit = P[i][bit].next;
                    break;
                }
            }
            P[i][ii].need2overflow = c;
            P[i][ii].next = bit;
            //cout << "[" << i << "][" << ii << "]: " << P[i][ii].need2overflow << ", " << P[i][ii].next << endl;
        }
    }
    long long result = -1;
    ull upper = 0;
    ull lower = 1;
    ull count = 1;
    ull current_upper = upper;
    ull current_lower = lower;
    ull current_count = count;
    ull upc = popcount(upper);
    while (true) {
        current_upper = upper;
        current_lower = lower;
        current_count = count;
        upc = popcount(upper);
        count += P[upc][lower].need2overflow;
        lower = P[upc][lower].next;
        upper++;
        ull pos = (upper << BITS_LOWER) + lower;
        if (pos >= n) { // 行き過ぎ
            // 一つ戻す
            count = current_count;
            upper = current_upper;
            lower = current_lower;
            pos = (upper << BITS_LOWER) + lower;
            // 普通に計算する
            while (true) {
                if (pos == n) {
                    result = count;
                    break;
                }
                else if (pos > n) break;
                pos += popcount(pos);
                count++;
            }
            break;
        }
    }
    cout << result << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX