ABC290感想（C, D）

C問題

入力を読み取るときに，setのデータ構造で読み取るようにすれば，読み込んだ段階でソートされていることになるので，これは一つテクニックとして覚えておきたい．std::setは任意の値を探したい時に，見つけたらそのインデックスを返すfindという関数を持っている．もしそのデータ構造の中に含まれていなかったらA.end()を返すのでそれを今回も利用した．また，std::vectorで似たようなことをやりたかったら，std::find(A.begin(), A.end(), i) == A.end()のように書く．その際，#include <algorithm>を忘れずに．

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

int main() {
  int N, K;
  std::cin >> N >> K;
  // set型にしておくことで，最初からソートされる
  std::set<int> A;
  for (int i = 0; i < N; i++) {
    int a;
    std::cin >> a;
    A.insert(a);
  }
  // std::sort(A.begin(), A.end());
  // Kが答えの時は，falseのままでKより小さい値が全て含まれる．
  for (int i = 0; i < K; i++) {
    if (A.find(i) == A.end()) {
      std::cout << i << std::endl;
      return 0;
    }
  }
  std::cout << K << std::endl;
  return 0;
}

D問題

自分的にはかなり難しかったが，緑レベルの問題なのか．．．という感じ．与えられた条件の操作を素直にやるだけだとTLEでうまくいかない．そこで上手い方法を考えるわけだが，最大公約数をうまく使うことで，O(1)で求めたい値を求められる．また，long long型にするのもポイントで，intだとオーバーフローによりエラーを出す．

#include <iostream>
#include <vector>

int mygcd(int a, int b) {
  if (b == 0) return a;
  return mygcd(b, a%b);
}

int main() {
  int T;
  std::cin >> T;
  for (int i = 0; i < T; i++) {
    int N, D, K;
    std::cin >> N >> D >> K;
    K--;
    int g = mygcd(N, D);
    int times = N / g;
    std::cout << (long long)D*K % N + K / times << std::endl;
  }
  return 0;
}