Atcoder Biginner Contest 190 (ABC190)振り返り

 Atcoder Biginner Contest 190に参加しました。

atcoder.jp

A問題

A - Very Very Primitive Game

　場合分けする。飴が多いほうが勝ち、飴の数が同じなら後手が勝ち。
まとめると高橋君が先手(C=0)かつ高橋君の飴が多い(A>B)のとき高橋君の勝ち。または高橋君が後手(C=1)かつ高橋君の飴の数が青木君以上(A>=B)のとき高橋君が勝ち。それ以外では青木君が勝ち。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if(C==0 && A>B)cout << "Takahashi" << endl;
  else if(C==1 && A>=B)cout << "Takahashi" << endl;
  else cout << "Aoki" << endl;
}

B問題

B - Magic 3

　かつとなるが存在するか全探索する。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, S, D;
  cin >> N >> S >> D;
  vector<int>X(N);
  vector<int>Y(N);
  for(int i=0; i<N; i++)cin >> X[i] >> Y[i];
  
  for(int i=0; i<N; i++){
    if(X[i]<S && Y[i]>D){
      cout << "Yes" << endl;
      return 0;
    }
  }
  
  cout << "No" << endl;
}

C問題

C - Bowls and Dishes

　皿か皿かを選ぶのでbit全探索をすれば良さそう。Kが16以下なので高々2¹⁶~6×10⁴であり、N, M, Kについてもループするので計算量は 程度となる。最大でも10⁷に満たないので時間は余裕。
　

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, S, D;
  cin >> N >> S >> D;
  vector<int>X(N);
  vector<int>Y(N);
  for(int i=0; i<N; i++)cin >> X[i] >> Y[i];
  
  for(int i=0; i<N; i++){
    if(X[i]<S && Y[i]>D){
      cout << "Yes" << endl;
      return 0;
    }
  }
  
  cout << "No" << endl;
}

D問題

D - Staircase Sequences

　この問題は2Nの約数を求める問題に言い換えることができる(by 公式解説)。
　ただ、直感的には次のような別解のほうが分かりやすいと思う。

　まず簡単のために、正の数(1以上)の範囲について考える。項数iの等差数列は、階段部分と長方形部分に分けることができる。逆にNから階段部分を除いた部分がiで割り切れるならば一辺がiの長方形が存在するため、この数列が存在する。

　次に負の数を含めた整数全体について考える。正の数の範囲で考えたそれぞれの数列に対して、増加分を相殺するような適切な範囲を含めることで必ず1つだけ対応する数列が存在している。つまり求める全体の数列の個数は正の範囲に限定した場合のちょうど2倍存在する。

以上をまとめると

を満たすiの個数を数えて2倍したものが求める答えである。

#include <bits/stdc++.h>
using namespace std;

int main() {
  long long N;
  cin >> N;
  long long count =0;
  for(long long i=1; i*(i+1)/2<=N; i++){
    if((N-i*(i+1)/2)%i==0)count ++;
  }
  
  cout << count*2 << endl;
}

感想

　最近のA問題の中で一番難しいA。普通のB。初めてbit全探索を実装できたC(時間がかかった)。制約を見て計算量くらいになるはずだから、から逆算したD。ふいんきしか分からなかったE。 　bit全探索できたことが一番成長した。