結果

問題 No.3 ビットすごろく
ユーザー nanae
提出日時 2017-06-16 18:44:06
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,826 bytes
コンパイル時間 691 ms
コンパイル使用メモリ 103,160 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 20:12:01
合計ジャッジ時間 1,891 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.container, std.math, std.typecons;

immutable int mod = 10^^9 + 7;
immutable int inf = 20000;

int N;

void main() {
    N = readln.chomp.to!int;

    auto d = new int[](N);
    auto q = Queue!(int)(N + 10);

    fill(d, inf);
    d[0] = 1;
    q.push(0);

    int pos;

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

        if (pos == N - 1) break;

        int dx = popcnt(pos + 1);

        if (pos + dx < N && d[pos + dx] == inf) {
            d[pos + dx] = d[pos] + 1;
            q.push(pos + dx);
        }

        if (pos - dx >= 0 && d[pos - dx] == inf) {
            d[pos - dx] = d[pos] + 1;
            q.push(pos - dx);
        }
    }

    debug {
        stderr.writeln(d);
    }

    writeln(d[N - 1] < inf ? d[N - 1] : -1);
}

int popcnt(int x) {
    return x > 0 ? popcnt(x>>1) + (x & 1) : 0;
}

unittest {
    assert(popcnt(0) == 0);
    assert(popcnt(3) == 2);
    assert(popcnt(15) == 4);
    assert(popcnt(24) == 2);
    assert(popcnt(7) == 3);
    assert(popcnt(8) == 1);
}

struct Queue(T) {
private:
    int N, head, tail;
    T[] data;

public:
    this(int size)
    {
        N = size + 1;
        data = new T[](N);
    }

    bool empty() @property
    {
        return head == tail;
    }

    bool full() @property
    {
        return (tail + 1) % N == head;
    }

    void push(T x) @property
    {
        assert(!full);
        data[tail++] = x;
        tail %= N;
    }

    void pop() @property
    {
        assert(!empty);
        (head += 1) %= N;
    }

    T front() @property
    {
        assert(!empty);
        return data[head];
    }

    void clear() @property
    {
        head = tail = 0;
    }

    int length() @property
    {
        return (tail - head + N) % N;
    }
}
0