📖

ABC226 C - Martial artist C++解答例

5 min read

AtCoder Beginner Contest 226 C - Martial artistをC++で解きます。

問題

問題文をAtCoderのページより引用します。

問題文

高橋くんは武術家です。武術家の覚えられる技はN個あり、技1, 2, \ldots, Nと名前がついています。1 \leq i \leq Nについて、技iを習得するには時間T_iの修練が必要で、さらに、修練の開始時点でA_{i, 1}, A_{i, 2}, \ldots, A_{i, K_i}をすでに習得している必要があります。ここで、1 \leq j \leq K_iについて、A_{i, j} < iであることが保証されます。

高橋くんは時刻0の時点で技を1つも覚えていません。高橋くんは同時に1つの技に対する修練しかできず、また、一度始めた修練を途中でやめることもできません。高橋くんが技Nを習得するのに必要な時間の最小値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq T_i \leq 10^9
  • 0 \leq K_i < i
  • 1 \leq A_{i, j} < i
  • \sum_{i=1}^N K_i \leq 2 \times 10^5
  • A_{i, 1}, A_{i, 2}, \ldots, A_{i, K_i}はすべて異なる。
  • 入寮は全て整数である。

解答例

依存関係はグラフで表現する

問題文からして複雑な問題ですが、とりあえず見通しを立てるところから始めます。

1からNまでの番号がついた技があって、ある技i(1\leq i \leq N)を習得するためにはK_i個の下位の技を覚えていなければならないという制約条件が課されています[1]換えると、技iは0個以上の技A_{i, 1}, A_{i, 2}, \ldots, A_{i, K_i}に依存していると言えます。

このような頂点同士の依存関係を表現するには有向グラフを使うのが有効であると考えられます。

Nを覚えるために必要な全部の技は?

高橋くんの目的は最上位の技である技Nを覚えることです。技Nを覚えるために必要な技以外は覚える必要はありません。

技の依存関係をグラフで表したとき、Nを覚えるために必要な技は、Nから出ている有向辺が接続されている頂点集合であると言うことができます。また、そのそれぞれの頂点から伸びている有向辺が繋がっているノードもまた、Nを覚えるために必要となります。

従って、頂点Nから有向辺を辿って到達可能な全ての頂点を覚えなければ、技Nは覚えられないということがわかります。

これらの技は頂点Nからグラフを探索することで求めることができます。BFSでもDFSでもどちらでも可能です。

覚えるべき技を全部習得するのにかかる時間

次に、技Nを覚えるために必要な技を全て習得するのにかかる時間を求めます。
便宜上、頂点Nから到達可能な全てのノードの集合をSとし、Sの各要素を番号が小さい順にV_1, V_2, \ldots, V_{|S|}と名付けることにします。

ここで、集合Sに属する頂点V_1, V_2, \ldots, V_{|S|}のうち、最初に習得することができるのは番号が最も若い頂点V_1であることがわかります。
何故なら、技の依存関係は大きい番号から小さい番号にのみ伸びており、また集合Sに属する頂点には必ず依存関係が存在するからです。

また、V_1を覚えた後に習得することができるのは、V_1の次に番号の若い頂点V_2です。
これを繰り返していくと、集合Sに属する頂点(技)を全て覚えるためには、番号の若い順に習得していけばよいことがわかります。

実際に実装する

以上の考えを実際に実装します。問題を解くにあたって、2つのステップに分けて実装する必要があります。

  1. Nから到達可能な頂点を列挙する
  2. 列挙した頂点を番号が小さい順に並べ、習得にかかる時間を足し合わせていく

1は簡単なグラフ探索で行えます。「Nから到達可能か?」を表す配列を用意して探索を行うことで求めることができます。
1の結果を元に2の計算を行うことで、この問題を解くことができます。

実装例

実装例を以下に示します。

c.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
 
int main() {
  int64_t N;
  std::cin >> N;
  std::vector<int64_t> T(N);
  std::vector<std::vector<int64_t>> graph(N);
  for (int64_t i = 0; i < N; i++) {
    int64_t t, k;
    std::cin >> t >> k;
    T.at(i) = t;
    for (int64_t j = 0; j < k; j++) {
      int64_t a;
      std::cin >> a;
      // 0-indexedでグラフを構築する
      graph.at(i).push_back(a - 1);
    }
  }
 
  // 頂点Nから到達可能な頂点を幅優先探索で探す
  std::vector<bool> reachable(N, false);
  // 頂点Nも含む
  reachable.at(N - 1) = true;
  std::queue<int64_t> candidate;
  candidate.push(N - 1);
 
  while (!candidate.empty()) {
    int64_t node = candidate.front();
    candidate.pop();
 
    for (int64_t next_node : graph.at(node)) {
      if (reachable.at(next_node)) continue;
      reachable.at(next_node) = true;
      candidate.push(next_node);
    }
  }
 
  // 番号が小さい順に習得所要時間を足し合わせていく
  int64_t answer = 0;
  for (int64_t i = 0; i < N; i++) {
    if (reachable.at(i)) {
      answer += T.at(i);
    }
  }
 
  std::cout << answer << std::endl;
 
  return 0;
}

実際に提出したコードはこちら

おまけ:DFSによる解法

Nから到達可能な頂点のうち、番号の若い順から習得所要時間を足し合わせるという計算を行えばこの問題を解くことができるため、構築したグラフに対して深さ優先探索を行うだけでもこの問題を解くことができます。

c.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
void dfs(std::vector<std::vector<int64_t>>& graph,
            std::vector<bool>& acquired,
            std::vector<int64_t>& T,
            int64_t& total_time,
            int64_t current_node)
{
  // 頂点iの技が依存している技を先に覚えに行く
  for (auto next_node : graph.at(current_node)) {
    if (acquired.at(next_node) == false) {
      dfs(graph, acquired, T, total_time, next_node);
    }
  }
  // 依存関係が解決したら技iを覚える
  acquired.at(current_node) = true;
  // 技iを覚えるのにかかった時間を足し合わせる
  total_time += T.at(current_node);
}
 
int main() {
  int64_t N;
  std::cin >> N;
  std::vector<int64_t> T(N);
  std::vector<std::vector<int64_t>> graph(N);
  for (int64_t i = 0; i < N; i++) {
    int64_t t, k;
    std::cin >> t >> k;
    T.at(i) = t;
    for (int64_t j = 0; j < k; j++) {
      int64_t a;
      std::cin >> a;
      graph.at(i).push_back(a - 1);
    }
  }
 
  // 探索済み(習得済み)かどうかを管理する配列
  std::vector<bool> acquired(N, false);
  int64_t answer = 0;
  dfs(graph, acquired, T, answer, N - 1);
 
  std::cout << answer << std::endl;
 
  return 0;
}

実際に提出したコードはこちら

脚注
  1. 4つ目の制約条件1 \leq A_{i, j} < iからこのことがわかります。ある技iを覚えようとしたとき、技iを覚えるために必要となる技のリストA_{i, 1}, A_{i, 2}, \ldots, A_{i, K_i}の各要素A_{i, j}(1 \leq j \leq K_i)の値はiより小さくなるので、技iを覚えるためにiより上位の技は関係ないということが示されています。 ↩︎

Discussion

ログインするとコメントできます