接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195）

AtCoderBeginnerContest AtCoderBeginnerContest195 ABC ABC195

atcoder.jp

A - Health M Death

$ H $ が $ M $ で割り切れればYes そうでないなら No
提出コード

void solve(){
    int M, H;
    cin >> M >> H;
    if(H % M == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Many Oranges

難しい
選んだ個数を $ i $ とすると達成できる重さの範囲は $ i \times A \leq x \leq i \times B $ を満たす $ x $ となる
よって $ i $ を全探索をし $ i \times A \leq 1000W \leq i \times B $ を満たす最小と最大の $ i $ を求めればいい
提出コード

void solve(){
    int A, B, W;
    cin >> A >> B >> W;
    W *= 1000;
    int mi = INF;
    int ma = 0;
    for(int i=1;i<=1e6;i++){
        if(i * A <= W and W <= i * B){
            chmax(ma, i);
            chmin(mi, i);
        }
    }
    if(mi == INF) cout << "UNSATISFIABLE" << endl;
    else cout << mi << " " << ma << endl;
}

C - Comma

$ 10 ^ 3 \leq x \lt 10 ^ 6 $ はコンマ1個、 $ 10 ^ 6 \leq x \lt 10 ^ 9 $ はコンマ2個・・・
のようになるのでif文などで数えればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    ll ans = 0;
    vector<ll> v[4];
    if(N >= (ll)1e3){
        if(N < (ll)1e6) ans += N - 1e3 + 1;
        else ans += 1e6 - 1e3;
    }
    if(N >= (ll)1e6){
        if(N < (ll)1e9) ans += 2 * (ll)(N - 1e6 + 1);
        else ans += 2 * (ll)(1e9 - 1e6);
    }
    if(N >= (ll)1e9){
        if(N < (ll)1e12) ans += 3 * (ll)(N - 1e9 + 1);
        else ans += 3 * (ll)(1e12 - 1e9);
    }
    if(N >= (ll)1e12){
        if(N < (ll)1e15) ans += 4 * (ll)(N - 1e12 + 1);
        else ans += 4 * (ll)(1e15 - 1e12);
    }
    if(N == (ll)1e15) ans += 5;
    cout << ans << endl;
}

D - Shipping Center

価値が大きいものから順に箱に詰めていく
詰める箱は、今詰めようとしているものが入る最小の箱に入れていけばいい
提出コード

void solve(){
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> W(N), V(N);
    REP(i,N) cin >> W[i] >> V[i];
    vector<int> X(M);
    REP(i,M) cin >> X[i];
    while(Q--){
        int L, R;
        cin >> L >> R;
        --L, --R;
        vector<int> idx(N);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b){
            return V[a] > V[b];
        });
        vector<int> idx2(M);
        iota(idx2.begin(), idx2.end(), 0);
        sort(idx2.begin(), idx2.end(), [&](int a, int b){
            return X[a] < X[b];
        });
        vector<bool> used(M);
        ll ans = 0;
        for(auto i : idx){
            for(auto j : idx2){
                if(L <= j and j <= R) continue;
                if(!used[j] and X[j] >= W[i]){
                    ans += V[i];
                    used[j] = true;
                    break;
                }
            }
        }
        cout << ans << endl;
    }
}

E - Lucky 7 Battle

$ dp[i][j] := $ i回目の操作が終わったあとに $ T = j \pmod{7} $ になる状態があるかどうかをDPする
$ dp[N][0] $ となればTakahashiの勝ちとなるので後ろから考えると、$ S_N = T $ のとき $ 10r = 0 \pmod{7} $ もしくは、 $ 10r + S_{N} = 0 \pmod{7} $ のときTakahashiの勝ち
$ S_N = A $ のとき $ 10r \neq 0 \pmod{7} $ かつ $ 10r + S_{N} \neq 0 \pmod{7} $ のときAokiの勝ちとなるのでTakahashiが勝つには$ 10r = 0 \pmod{7} $ かつ $ 10r + S_{N} = 0 \pmod{7} $ であればいい
そのため、後ろからDPをしていき最終的に $ dp[0][0] $ が勝ちになるような状態が存在すればTakahashiの勝ち、そうでないならAokiの勝ちとなる
提出コード

void solve(){
    int N;
    string S, X;
    cin >> N >> S >> X;
    vector dp(N+1, vector<int>(7, 0));
    dp[N][0] |= 1;
    for(int i=N-1;i>=0;i--){
        int c = S[i] - '0';
        REP(k,7){
            if(X[i] == 'T') dp[i][k] |= (dp[i+1][(10*k)%7] or dp[i+1][(10*k+c)%7]);
            else dp[i][k] |= (dp[i+1][(10*k)%7] and dp[i+1][(10*k+c)%7]);
        }
    }
    cout << (dp[0][0] ? "Takahashi" : "Aoki") << endl;
}

F - Coprime Present

$ A \leq m \lt n \leq B $ を満たす $ (n, m) $ について
$ gcd(n, m) = gcd(n-m, m) \leq n - m \leq B - A $ が成り立つため、$ n, m $ が互いに素でない時、$ 2 \leq x \leq B - A $ を満たすある素数 $ x $ の倍数となる
したがって、$ 2 \leq x \leq B - A $ を満たす素数 $ x $ の倍数が高々1個しか含まれないような集合の数を求めればいい
$ dp[state] := $ 素数 $ x $ の倍数を選んだ状態が $ state $ のときの場合の数として、bitDPで求めればいい
提出コード

void solve(){
    ll A, B;
    cin >> A >> B;

    vector<bool> used(73);
    vector<int> prime;
    for(int i=2;i<=72;i++){
        if(used[i]) continue;
        prime.emplace_back(i);
        for(int j=2*i;j<=72;j+=i) used[j] = true;
    }
    int n = prime.size();
    vector dp(1<<n, 0LL);
    dp[0] = 1;
    ll ans = 0;
    for(ll j=A;j<=B;j++){
        int bit = 0;
        REP(k,n){
            if(j % prime[k] == 0){
                bit |= (1 << k);
            }
        }
        REP(i,1<<n){
            if((bit & i) > 0) continue;
            dp[i|bit] += dp[i];
        }
    }
    REP(i,1<<n) ans += dp[i];
    cout << ans << endl;
}