ABC289感想(C, D, E) - takumi9のブログ

C問題

bit全探索で解く問題．2^m-1の選び方がある問題だから，bit全探索で解く問題だとは思ったが，部分集合を足し合わせた集合に1~Nが全て含まれているかどうかを判別するアルゴリズムが思いつかなかった．

解答を見て納得した．std::setというライブラリを使ってそこに値をinsertで格納していくことでそれを実現している．std::setというライブラリは，そこに格納された値は自動的にソートされ，さらに重複した値は新しく格納されないという特徴を持っている（multisetというライブラリなら重複を許容する）．つまり，部分集合に含まれる値を全てset配列に格納していき，その配列の長さがNになるかどうかで判別問題を解いている．

#include <iostream>
#include <vector>
#include <set>

int main() {
  int N, M;
  std::cin >> N >> M;
  std::vector<std::vector<int> > C;
  for (int i = 0; i < M; i++) {
    int c_num;
    std::vector<int> a_vec;
    std::cin >> c_num;
    for (int i = 0; i < c_num; i++) {
      int tmp;
      std::cin >> tmp;
      a_vec.push_back(tmp);
    }
    C.push_back(a_vec);
  }
  int result = 0;
  for (int i = 0; i < (1 << M); i++) {
    std::set<int> S;
    for (int j = 0; j < M; j++) {
      if ((i >> j) & 0b1) {
        for (auto& v: C[j]) S.insert(v);
      }
    }
    if (S.size() == N) 
      result++;
  }
  std::cout << result << std::endl;
  return 0;
}

D問題

dpで解くことはわかったが，二次元だと勝手に思い込んだせいで，メモリオーバー・時間オーバーでずっと通らなかった．縦軸を回数で取っていたが，全くそうする必要がないことに気づき，一次元で実装し直したら通った．ただ以下の自分の実装だと，初期値の0, 餅があって通れない段を1, 通れる段を2としていて，3種類も使う必要がないのではと思っていて，解答の実装を確認したら，最初に1で初期化した後に餅がある段は0にしている．これはどうせそれぞれの段について改めて調べていくから初期値は1にして問題ないという魂胆．

#include <iostream>
#include <vector>

int main() {
  int N, M;
  std::vector<int> A;
  std::vector<int> B;
  int X;
  std::cin >> N;
  for (int i = 0; i < N; i++) {
    int tmp;
    std::cin >> tmp;
    A.push_back(tmp);
  }
  std::cin >> M;
  for (int i = 0; i < M; i++) {
    int tmp;
    std::cin >> tmp;
    B.push_back(tmp);
  }
  std::cin >> X;
  // 2=ok, 1=no, 0=first
  std::vector<int> dp(X+1, 0);
  for (auto &val: B) {
    dp.at(val) = 1;
  }
  // initialize
  dp.at(0) = 2;
  for (int i = 1; i < X+1; i++) {
    if (dp.at(i) == 1) continue;
    for (auto &val: A) {
      if (i - val >= 0 && dp.at(i-val) != 1) {
        if (dp.at(i-val) == 2) {
          dp.at(i) = 2;
        }
      }
    }
  }
  if (dp[X] == 2) 
    std::cout << "Yes" << std::endl;
  else
    std::cout << "No" << std::endl;
  return 0;
}

E問題

二つの座標を持ってして一つの状態として，それを遷移させてBFSを行うという方法．完全に解法がわからず解答を見てから実装をした．遷移可能な状態は全て探索しているので，計算量が大きくなると思いきや，意外とそこまで大きくはならないというのもポイントかも．計算量の議論も厳密にできるようになりたい．

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

#define myprint(st) std::cout << st << std::endl;

const int inf = std::numeric_limits<int>::infinity();

int main() {
  int T;
  std::cin >> T;
  for (int i = 0; i < T; i++) {
    int N, M;
    std::cin >> N >> M;
    std::vector<int> C(N);
    for (int j = 0; j < N; j++) {
      std::cin >> C.at(j);
    }
    // 可変長のベクトルを要素にもつマトリックスを作る．データ構造に関するポイント．
    std::vector<std::vector<int> > Matr(N, std::vector<int>(0));
    for (int j = 0; j < M; j++) {
      int u, v;
      std::cin >> u >> v;
      // 頂点のnumberが実際の値から1を引いたものだから．
      Matr.at(u-1).push_back(v-1);
      Matr.at(v-1).push_back(u-1);
    }

    std::queue<std::pair<int, int> > A;
    A.push(std::make_pair(0, N-1));
    std::vector<std::vector<int> > dist(N, std::vector<int>(N, -1));
    dist.at(0).at(N-1) = 0;
    while (A.size() > 0) {
      int a, b;
      a = A.front().first;
      b = A.front().second;
      A.pop();
      int d = dist[a][b];
      for (auto &val_a: Matr.at(a)) {
        for (auto &val_b: Matr.at(b)) {
          if (C.at(val_a) == C.at(val_b) || dist.at(val_a).at(val_b) != -1) 
            continue;
          A.push(std::make_pair(val_a, val_b));
          dist[val_a][val_b] = d+1;
        }
      }
    }
    std::cout << dist[N-1][0] << std::endl;
  }
  return 0;
}