Div.1 A ＆ Div.2 C : Game

問題概要

3 台の PC と n 題の問題があり、各問題はどの PC で解けるか決まっている。また、問題同士も依存関係があり、特定の問題群が終わっていないと解けない問題がある。各問題を解くのに 1 時間ずつ、PC の移動は PC1→PC2→PC3→PC1→… の移動に 1 時間ずつかかる。
開始する時の PC はどこにいても構わないとする時、最短でどの程度の時間がかかるか。ただし PC に問題を解かせつつ移動することはできない。

考え方

今使っている PC で解ける問題があるとき、それをとりあえず解くことにデメリットはない。また今解き終わった問題で新しく解けるようになった問題が 2 個先の PC にあっても、実は 1 個先の PC に行って、そこで解ける問題があるかチェックしたあとで移動しても損はない。
なので特定の PC からスタートして、解ける問題を解いてみて移動、を繰り返せば良い。あとは依存関係(もう依存先の問題が終わっているので解ける、という判断)の処理を間違えないようにすれば大丈夫。

コード

#include <iostream>
#include <vector>
using namespace std;

int StartFrom(int from, vector<vector<int> > a, vector<int> c) {
  const int n = c.size() - 1;
  int cost = 0, rem = n;
  for (int p = from; rem; p = p % 3 + 1) {
    for (int i = 1; i <= n; ++i) {
      if (c[i] != p) continue;
      if (a[i].size() == 0) {
        c[i] = 0;  // task i done
        for (int j = 1; j <= n; ++j)
          for (int k = a[j].size() - 1; k >= 0; --k)
            if (a[j][k] == i) a[j].erase(a[j].begin() + k);
        ++cost;
        --rem;
        i = 0;
      }
    }
    if (rem) ++cost;
  }
  return cost;
}

int main(void) {
  int n;
  cin >> n;
  vector<int> c(n + 1);
  for (int i = 1; i <= n; ++i) cin >> c[i];
  c[0] = 0;

  vector<vector<int> > a(n + 1);
  for (int i = 1; i <= n; ++i) {
    int k;
    cin >> k;
    a[i].resize(k);
    for (int j = 0; j < k; ++j) cin >> a[i][j];
  }

  int ret = n * 10;
  for (int start = 1; start <= 3; ++start) {
    int cost = StartFrom(start, a, c);
    ret = min(cost, ret);
  }
  cout << ret << "\n";

  return 0;
}