AtCoder Beginner Contest 142 （ABC142）

5完2ペナでパフォ1468で無事入水しました（やったね）
後日入水記事も書きます！

A - Odds of Oddness

答えは奇数の数 / Nになります
奇数の数え方は(N + 1) / 2で出来ますが，制約が小さいのでforで数えてもいいですね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double N;
    cin >> N;
    double ans = (((int)N + 1) / 2) / N;
    printf("%.8lf\n", ans);
}

B - Roller Coaster

forを回してK以上のものを数える
Aのほうが時間かかった...
[提出コード]

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    int ans = 0;
    cin >> N >> K;
    REP(i,N){
        int h;
        cin >> h;
        if(h >= K) ans++;
    }
    cout << ans << endl;
}

C - Go to School

ソートしたあとのインデックスを答える
こういうのは別にインデックスの配列を作ってラムダ関数とかでソートするのが楽な気がします
類題->B - Guidebook
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<int> idx(N);
    iota(idx.begin(),idx.end(),0);
    sort(idx.begin(), idx.end(),[&](int x, int y){return A[x] < A[y];});
    REP(i,N){
        cout << idx[i] + 1 << " ";
    }
    cout << endl;
}

D - Disjoint Set of Common Divisors

AtCoderだなあって思った問題
AとBの公約数を考える
AとBの公約数はAとBの最大公約数の約数に含まれる
公約数は互いに素であるものを数えるので最大公約数の素因数の個数がわかればいい
これに公約数が1の場合を足したものが答え
提出コード

ll gcd(ll x, ll y){
  return y ? gcd(y, x%y) : x;
}

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));//p^num
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B;
    cin >> A >> B;
    ll GCD = gcd(A, B);
    auto res = prime_factorize(GCD);

    cout << res.size() + 1 << endl;
}

E - Get Everything

いわゆるbitDPと呼ばれるもの？見た瞬間DPだろうなあっていいながら貪欲で2WA生やしたのはなんですか
dp[state] := 状態がstateに出来るときの最小費用としてbitDPをします
今の状態からbitが立つものがあれば chmin(dp[nextState], dp[state] + a[state])のように更新していきます
提出コード

ll a[1010], b[1010];
ll C[1010][20];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    REP(i,M){
        cin >> a[i] >> b[i];
        REP(j,b[i]){
            cin >> C[i][j];
            C[i][j]--;
        }
    }
    vector<ll> dp((1<<N), LINF);
    dp[0] = 0;
    REP(i,(1<<N)){
        REP(j,M){
            int tmp = i;
            REP(k, b[j]){
                tmp |= (1 << C[j][k]);
            }
            chmin(dp[tmp], dp[i] + a[j]);
        }
    }
    ll ans = dp[(1<<N)-1];
    if(ans == LINF) cout << -1 << endl;
    else cout << ans << endl;
}

おわりに

コンテスト本番中に初めてDPを通せて最近DPやってて身についたかなあって感想
欲を言えばもう少し早くときたかったけど5完で入水出来たので良しとします
水色で満足せず青，黄と上を目指していきたいね
入水記事何書こう