結果

問題 No.3 ビットすごろく
コンテスト
ユーザー not_522
提出日時 2015-07-16 16:41:02
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 5,330 bytes
コンパイル時間 1,800 ms
コンパイル使用メモリ 175,100 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-01 07:27:14
合計ジャッジ時間 2,627 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

int countBit(int n) {
  return __builtin_popcount(n);
}

int countBit(unsigned int n) {
  return __builtin_popcount(n);
}

int countBit(long long n) {
  return __builtin_popcountll(n);
}

int countBit(unsigned long long n) {
  return __builtin_popcountll(n);
}

struct Edge {
  typedef int CostType;
  const static int cost = 1;
  int from, to;
  Edge(int from, int to) : from(from), to(to) {};
};

template<typename Cost> struct WeightedEdge : public Edge {
  typedef Cost CostType;
  Cost cost;
  WeightedEdge(int from, int to, Cost cost = 0) : Edge(from, to), cost(cost) {}
};

template<typename Capacity> struct ResidualEdge : public Edge {
  typedef Capacity CapacityType;
  Capacity cap;
  int rev;
  ResidualEdge(int from, int to, Capacity cap) : Edge(from, to), cap(cap) {}
  ResidualEdge reverse() const {return ResidualEdge(to, from, 0);}
};

template<typename Capacity, typename Cost> struct WeightedResidualEdge : public ResidualEdge<Capacity> {
  Cost cost;
  WeightedResidualEdge(int from, int to, Capacity cap, Cost cost) : ResidualEdge<Capacity>(from, to, cap), cost(cost) {}
  WeightedResidualEdge reverse() const {return WeightedResidualEdge(this->to, this->from, 0, -cost);}
};

template<typename Edge> class Graph {
public:
  typedef Edge EdgeType;
  virtual int size() const = 0;
  template<typename... Args> void addEdge(Args...) {}
  template<typename... Args> void addUndirectedEdge(Args...) {}
  virtual vector<Edge> getEdges() const = 0;
  virtual vector<Edge> getEdges(int from) const = 0;
  virtual vector<Edge> getEdges(int from, int to) const = 0;
  virtual int getDegree(int v) const = 0;
};

template<typename Edge> class AdjacencyList : public Graph<Edge> {
protected:
  vector<vector<Edge>> graph;

public:
  AdjacencyList(int n) : graph(n) {}

  int size() const {
    return graph.size();
  }
  
  template<typename... Args> void addEdge(Args... args) {
    Edge edge(args...);
    graph[edge.from].emplace_back(edge);
  }

  template<typename... Args> void addUndirectedEdge(Args... args) {
    Edge edge(args...);
    addEdge(edge);
    swap(edge.from, edge.to);
    addEdge(edge);
  }

  vector<Edge> getEdges() const {
    vector<Edge> res;
    for (const auto& edges : graph) {
      res.insert(res.end(), edges.begin(), edges.end());
    }
    return res;
  }

  vector<Edge> getEdges(int from) const {
    return graph[from];
  }

  vector<Edge> getEdges(int from, int to) const {
    vector<Edge> res;
    for (const auto& edge : graph[from]) {
      if (edge.to == to) res.emplace_back(edge);
    }
    return res;
  }

  int getDegree(int v) const {
    return graph[v].size();
  }

  vector<Edge>& operator[](int v) {
    return graph[v];
  }
};

template<typename Graph, typename State> class Search {
protected:
  typedef typename Graph::EdgeType Edge;

  const Graph graph;
  vector<bool> visited;

  virtual void push(const State&) = 0;
  virtual State next() = 0;
  virtual bool isRunning() = 0;

  virtual void visit(const State&) {}
  virtual bool canPruning(const State&) {return false;}

public:
  Search(const Graph& graph) : graph(graph), visited(graph.size(), false) {}

  void solve(int from) {
    push(State(from));
    while (isRunning()) {
      State now = next();
      int pos = now.getPos();
      if (visited[pos]) continue;
      visited[pos] = true;
      visit(now);
      for (const Edge& edge : graph.getEdges(pos)) {
        State nextState = now.next(edge);
        if (visited[nextState.getPos()]) continue;
        if (canPruning(nextState)) continue;
        push(nextState);
      }
    }
  }

  bool isReachable(int v) {
    return visited[v];
  }
};

template<typename Edge> struct BFSState {
  int pos, prv;

  BFSState(int pos, int prv = -1) : pos(pos), prv(prv) {}
  
  BFSState next(const Edge& edge) const {
    return BFSState(edge.to, pos);
  }

  int getPos() {
    return pos;
  }
};

template<typename Graph, typename State = BFSState<typename Graph::EdgeType>> class BFS : public Search<Graph, State> {
protected:
  typedef typename Graph::EdgeType Edge;

private:
  queue<State> que;
  
  void push(const State& state) {
    que.push(state);
  }
  
  State next() {
    State now = que.front();
    que.pop();
    return now;
  }
  
  bool isRunning() {
    return !que.empty();
  }

public:
  BFS(const Graph& graph) : Search<Graph, State>(graph) {}
};

namespace bfs_distance {
  template<typename Graph> class BFSDistance : public BFS<Graph> {
  private:
    typedef BFSState<typename Graph::EdgeType> State;

    void visit(const State& state) {
      if (state.prv != -1) dis[state.pos] = dis[state.prv] + 1;
    }

  public:
    vector<int> dis;

    BFSDistance(const Graph& graph) : BFS<Graph>(graph), dis(graph.size(), 0) {}
  };
}

template<typename Graph> inline bfs_distance::BFSDistance<Graph> bfsDistance(const Graph& graph, int from) {
  bfs_distance::BFSDistance<Graph> bfs(graph);
  bfs.solve(from);
  return bfs;
}

int main() {
  typedef AdjacencyList<Edge> Graph;
  int n;
  cin >> n;
  Graph graph(n);
  for (int i = 0; i < n; ++i) {
    int c = countBit(i + 1);
    if (i + c < n) graph.addEdge(i, i + c);
    if (i - c >= 0) graph.addEdge(i, i - c);
  }
  auto info = bfsDistance(graph, 0);
  cout << (info.isReachable(n - 1) ? info.dis[n - 1] + 1 : -1) << endl;
}
0