結果

問題 No.3 ビットすごろく
ユーザー laoidn
提出日時 2023-04-23 21:37:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 9,716 bytes
コンパイル時間 4,565 ms
コンパイル使用メモリ 244,768 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 03:12:27
合計ジャッジ時間 6,218 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
#include <iostream>
#include <vector>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define fore(i, a) for (auto &i : a)
#define IN(a, x, b) (a <= x && x < b)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                        \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(0);
template <class T>
inline T CHMAX(T &a, const T b) {
  return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T &a, const T b) {
  return a = (a > b) ? b : a;
}
#include <algorithm>  // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>     // bitset
#include <cctype>     // isupper, islower, isdigit, toupper, tolower
#include <cstdint>    // int64_t, int*_t
#include <cstdio>     // printf
#include <deque>      // deque
#include <iostream>   // cout, endl, cin
#include <map>        // map
#include <queue>      // queue, priority_queue
#include <set>        // set
#include <stack>      // stack
#include <string>     // string, to_string, stoi
#include <tuple>      // tuple, make_tuple
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <utility>        // pair, make_pair
#include <vector>         // vector
using namespace std;
ll GCD(ll m, ll n) {
  // ベースケース
  if (n == 0) return m;
  // 再帰呼び出し
  return GCD(n, m % n);
}
ll minlong = 0;
long long Power(long long a, long long b, long long m) {
  long long p = a, Answer = 1;
  for (int i = 0; i < 63; i++) {
    ll wari = (1LL << i);
    if ((b / wari) % 2 == 1) {
      Answer = (Answer * p) % m;  // 「a の 2^i 乗」が掛けられるとき
    }
    p = (p * p) % m;
  }
  return Answer;
}
// a ÷ b を m で割った余りを返す関数
long long Division(long long a, long long b, long long m) {
  return (a * Power(b, m - 2, m)) % m;
}
// nCr mod 1000000007 を返す関数
long long nCk(ll n, ll r) {
  const long long M = 1000000007;
  // 手順 1: 分子 a を求める
  long long a = 1;
  for (int i = 1; i <= n; i++) a = (a * i) % M;
  // 手順 2: 分母 b を求める
  long long b = 1;
  for (int i = 1; i <= r; i++) b = (b * i) % M;
  for (int i = 1; i <= n - r; i++) b = (b * i) % M;
  // 手順 3: 答えを求める
  return Division(a, b, M);
}
using Interval = pair<ll, ll>;
// nCk mint を返す関数。
ll modnCk(ll n, ll r) {
  ll a = 1;
  for (ll i = n; i > n - r; i--) {
    a *= i;
    a /= n + 1 - i;
  }
  return a;
}
// 終点時間でsortをかけるのに必要(区間スケジューリング問題など)
bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; }
vll dycstra(vector<vector<pair<ll, ll>>> G, ll N, ll K) {
  vb kaku(N, false);
  vll cur(N, INF);
  cur[K] = 0;
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
  Q.push(make_pair(cur[K], K));
  while (!Q.empty()) {
    ll pos = Q.top().second;
    Q.pop();
    if (kaku[pos]) continue;
    kaku[pos] = true;
    for (ll i = 0; i < G[pos].size(); i++) {
      ll nex = G[pos][i].first;
      ll cost = G[pos][i].second;
      if (cur[nex] > cur[pos] + cost) {
        cur[nex] = cur[pos] + cost;
        Q.push(make_pair(cur[nex], nex));
      }
    }
  }
  return cur;
}
template <class T>
struct BIT {
  int n;                  // 要素数
  vector<T> bit[300000];  // データの格納先
  BIT(int n_) { init(n_); }
  void init(int n_) {
    n = n_ + 1;
    for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
  }
  void add_sub(int p, int i, T x) {
    for (int idx = i; idx < n; idx += (idx & -idx)) {
      bit[p][idx] += x;
    }
  }
  void add(int l, int r, T x) {  // [l,r) に加算
    add_sub(0, l, -x * (l - 1));
    add_sub(0, r, x * (r - 1));
    add_sub(1, l, x);
    add_sub(1, r, -x);
  }
  T sum_sub(int p, int i) {
    T s(0);
    for (int idx = i; idx > 0; idx -= (idx & -idx)) {
      s += bit[p][idx];
    }
    return s;
  }
  T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
  // sum'(i)=sum(i)-x(l-i)+xi(sum'(i)は加算後の合計値sum(i)測酸前の合計値)
  T query(int l, int r) { return sum(r - 1) - sum(l - 1); }
  // 任意の区間を計算することが可能これは[l,r)の区間和を計算している。
  int lower_bound(T w) {  // a_1 + a_2 + ... + a_x >= w となるような最小の x
                          // を求める(ただし a_i >= 0)
    if (w <= 0) {
      return 0;
    } else {
      int x = 0, r = 1;
      while (r < n) r = r << 1;
      for (int len = r; len > 0;
           len = len >> 1) {  // 長さlenは1段下るごとに半分に
        if (x + len < n && bit[x + len] < w) {  // 採用するとき
          w -= bit[x + len];
          x += len;
        }
      }
      return x + 1;
    }
  }
};
vll BFS(vvll &G, ll &x) {
  vll cut(G.size(), INF);
  queue<ll> Q;
  Q.push(x);
  cut[x] = 0;
  while (!Q.empty()) {
    ll a = Q.front();
    Q.pop();
    rep(i, G[a].size()) {
      if (cut[G[a][i]] > cut[a] + 1) {
        cut[G[a][i]] = cut[a] + 1;
        Q.push(G[a][i]);
      }
    }
  }
  return cut;
}
template <class Abel>
struct UnionFind {
  vector<int> par;
  vector<int> rank;
  vector<Abel> diff_weight;
  vector<int> siz;
  UnionFind(int n = 1, Abel SUM_UNITY = 0) { init(n, SUM_UNITY); }
  void init(int n = 1, Abel SUM_UNITY = 0) {
    par.resize(n);
    rank.resize(n);
    diff_weight.resize(n);
    siz.resize(n);
    for (int i = 0; i < n; ++i)
      par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY, siz[i] = 1;
  }
  int root(int x) {
    if (par[x] == x) {
      return x;
    } else {
      int r = root(par[x]);
      diff_weight[x] +=
          diff_weight[par[x]];  // 累積和をとることで重みがつけられる。
      return par[x] = r;
    }
  }
  Abel weight(int x) {
    root(x);                // 経路圧縮
    return diff_weight[x];  // 重みを返す
  }
  bool issame(int x, int y) {
    return root(x) == root(y);  // 通常時も同じ
  }
  // weight(y) - weight(x) = w となるように merge する
  bool merge(int x, int y, Abel w) {
    // x と y それぞれについて、 root との重み差分を補正
    w += weight(x);
    w -= weight(y);
    // x と y の root へ (x と y が既につながっていたら false を返すようにした)
    x = root(x);
    y = root(y);
    if (x == y) return false;
    // rank[x] >= rank[y] となるように x と y を swap (それに合わせて w
    // も符号反転します)これはUnion by
    // rankと呼ばれ根の高さをO(logN)で抑えられる手法である。
    if (rank[x] < rank[y]) swap(x, y), w = -w;
    // y (のroot) を x (のroot)
    // の下にくっつける(高さが低い方の根付き木を高いほうに併合する)
    if (rank[x] == rank[y]) ++rank[x];
    siz[x] += siz[y];
    par[y] = x;
    // x が y の親になるので、x と y の差分を diff_weight[y] に記録
    diff_weight[y] = w;
    return true;
  }
  Abel diff(int x, int y) { return weight(y) - weight(x); }
  int size(int x) { return siz[root(x)]; }
};
class SegmentTree {
 public:
  int dat[600000], siz = 1;
  // 要素 dat の初期化を行う（最初は全部ゼロ）
  void init(int N) {
    siz = 1;
    while (siz < N) siz *= 2;
    for (int i = 1; i < siz * 2; i++) dat[i] = 0;
  }
  // クエリ 1 に対する処理
  void update(int pos, int x) {
    pos = pos + siz - 1;
    dat[pos] = x;
    while (pos >= 2) {
      pos /= 2;
      dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
    }
  }
  // クエリ 2 に対する処理
  // u は現在のセル番号、[a, b) はセルに対応する半開区間、[l, r)
  // は求めたい半開区間
  int query(int l, int r, int a, int b, int u) {
    if (r <= a || b <= l) return -1000000000;  // 一切含まれない場合
    if (l <= a && b <= r) return dat[u];       // 完全に含まれる場合
    int m = (a + b) / 2;
    int AnswerL = query(l, r, a, m, u * 2);
    int AnswerR = query(l, r, m, b, u * 2 + 1);
    return max(AnswerL, AnswerR);
  }
};
void Yes(bool b) {
  if (b)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
vector<long long> yaku(long long n) {
  vector<long long> ret;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());  // 昇順に並べる
  return ret;
}
int main() {
  ll N, M, K, a, b, c;
  string S, T;
  cin >> N;
  vector<vector<pair<ll, ll>>> G(N);
  reps(i, 1, N) {
    bitset<32> p(i);
    a = i - p.count() - 1;
    b = i + p.count() - 1;
    if (a >= 0)
      G[i - 1].push_back(make_pair(a, 1));
    if (b <= N - 1)
      G[i-1].push_back(make_pair(b, 1));
  }
  vll A = dycstra(G,N, 0);
  if (A[N - 1] == INF) {
    cout << -1 << endl;
    return 0;
  }
  cout << A[N - 1] +1<< endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0