AtCoder Beginner Contest 142

はい． AtCoder Beginner Contest 142 です

A,B,C の3完でした． 今回もパフォーマンスもダメダメでレートも下がってしまいました…

DもEも見てたけど，両方解けずにダメでした．

A - Odds of Oddness

問題文

偶数が 個あるので，それを から引いて，全体の で割れば奇数である確率が分かりますね．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int n;
  cin >> n;
  cout << (n-(n/2))/(double)n << endl;
}

B - Roller Coaster

問題文

以上なら数え上げればいいので，入力を取りながら数えました．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
  int n,k;
  int ans =0;
  cin >> n >> k;
  for (int i=0; i<n; i++) {
    int h;
    cin >> h;
    if (h >= k) ans++;
  }

  cout << ans << endl;
}

C - Go to School

問題文

とりあえず入力とって， ] のデータを のデータを使ってソートして答え作りました．

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i=0; i<n; i++) cin>>a[i];
  vector<int> ans(n);
  iota(ans.begin(), ans.end(), 0);

  sort(ans.begin(), ans.end(), 
    [&](int x, int y) { return a[x] < a[y]; });

  for (int i=0; i<n; i++) cout << ans[i]+1 << endl;
}

D - Disjoint Set of Common Divisors

問題文

なんか GCD を求めて，それを素因数分解をしたりしてました(:3」∠)
GCD だと漏れるのでダメでしたね．
うーむ．思考ロックしていたのでダメでしたね．

もう少し丁寧に考えるべきでした．

E - Second Sum

問題文

が 12以下なので，全探索できる！と思って bitset で書いてたんだけど，ダメでした．
TLE が直せず…

解説をちらっと読んで DP と書いていたので書いてみました．
そうしたら通せました〜
DP という発想が欲しかった(:3」∠)

bitDP と言われているやつっぽいです．
bitでこういうことするのはよく考えるので DP という発想が欲しかった…

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <bitset>


using namespace std;

int main() {
  long n,m;
  cin >> n >> m;
  vector<long> costs;
  vector<long> open;
  vector<long> dp(1<<n, -1);

  for (int i=0; i<m; i++) {
    long a,b;
    cin >> a >> b;

    long cnt = 0;
    for (long j=0; j<b; j++) {
      long c;
      cin >> c;
      cnt += 1<<(c-1);
    }
    costs.push_back(a);
    open.push_back(cnt);
  }

  dp[0] = 0; 
  for (long i=0; i<m; i++) {
    dp[open[i]] = costs[i];
  }

  for (long i=0; i<(1<<n); i++) {
    if(dp[i]<0) continue;

    for (long j=0; j<m; j++) {
      long index = (i | open[j]);
      if (dp[index]<0) dp[index] = dp[i] + costs[j];
      else 
        dp[index] = min(dp[index], dp[i] + costs[j]);
    }
  }

  cout << dp[(1<<n)-1] << endl;
}

まとめ

レートが30も下がりました．
辛い…