接着剤の精進日記

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

AtCoder Beginner Contest 155(ABC155)

atcoder.jp

久しぶりにやらかして冷えた〜

A - Poor

A、B、Cの中なら一番難しかった(読解力さん…)
最初ソートしてa[0] == a[1] && a[0] != a[2]でよし!wをやってWA
それはそうなんですよね、C解いた後戻ってきてsetを使った
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    set<int> st;
    REP(i,3){
        int a;
        cin >> a;
        st.insert(a);
    }
    if(st.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Papers, Please

これも読解力?
言われたとおり偶数についてだけチェックする
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    string ans = "APPROVED";
    REP(i,N){
        if(A[i] % 2 == 0){
            if(A[i] % 3 == 0 || A[i] % 5 == 0) continue;
            else ans = "DENIED";
        }
    }
    cout << ans << endl;
}

C - Poll

慣れているとこれが一番早く解けそう
mapとかで出現回数を持っておいて、最大のものをvectorとかに入れてソートする
本番vectorに入れた後ソートしたけどmapでやってるからソートいらないよね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    map<string, int> mp;
    int ma = 0;
    REP(i,N){
        string s;
        cin >> s;
        mp[s]++;
        chmax(ma, mp[s]);
    }
    vector<string> ans;
    for(auto x : mp){
        if(x.second == ma) ans.push_back(x.first);
    }
    sort(ans.begin(), ans.end());
    REP(i,ans.size()) cout << ans[i] << endl;
}

D - Pairs

ぱっと見にぶたんとかでやりそうな雰囲気
負の数と交じるので処理が面倒くさそうだなあとなり一旦Eを見に行きEのほうが解けそうだったので結局本番中解かずに終わり
まだ実装してないので実装したらコード貼ります
[追記]
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    sort(A.begin(), A.end());
    auto f = [&](ll tar, ll a) -> ll{
        ll l = -1, r = N;
        while(r - l > 1){
            ll m = (r + l) >> 1;
            if(a * A[m] <= tar){
                if(a < 0) r = m;
                else l = m;
            }
            else{
                if(a < 0) l = m;
                else r = m;
            }
        }
        if(a < 0) return N - r;
        else return r;
    };

    ll l = -LINF, r = LINF;
    while(r - l > 1){
        ll m = (l + r) >> 1;
        ll cnt = 0;
        REP(i,N){
            cnt += f(m, A[i]);
            if(A[i] * A[i] <= m) cnt--;
        }
        if(cnt / 2 >= K) r = m;
        else l = m;
    }
    cout << r << endl;
}

E - Payment

取り敢えず桁ごとに独立で考える
その桁が5以下ならそのまま使って、6以上なら一桁繰り上げてお釣りを貰ったほうが良さそう
実装する、WA
実はこれだけじゃ不十分で、ある桁が5の時次の位が5以上かどうかで場合分けがもう一つ必要
本番中は、貪欲じゃ解けないじゃんってなってDPも書いてたんだけど結局遷移を間違えて通せなかった
提出コード(貪欲解)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int ans = 0;
    bool flg = false;
    reverse(S.begin(), S.end());
    int N = S.size();
    int cur = 0;
    REP(i,N){
        int a = S[i] - '0';
        a += cur;
        if(a < 5){
            ans += a;
            cur = 0;
        }
        else if(a > 5){
            ans += 10 - a;
            cur = 1;
        }
        if(a == 5){
            if(i < N - 1 && S[i+1] - '0' >= 5){
                ans += 10 - a;
                cur = 1;
            }
            else{
                ans += a;
                cur = 0;
            }
        }
        //cout << ans << endl;
    }
    if(cur > 0) ans++;
    cout << ans << endl;
}

提出コード(DP解)

int dp[1010101][2];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int ans = 0;
    reverse(S.begin(), S.end());
    int N = S.size();
    REP(i,1010101) dp[i][0] = dp[i][1] = INF;
    dp[0][0] = 0;
    REP(i,N){
        int a = S[i] - '0';
        chmin(dp[i+1][0], min(dp[i][0], dp[i][1]) + a);
        chmin(dp[i+1][1], min(dp[i][0] + 11 - a, dp[i][1] + 9 - a));
    }
    cout << min(dp[N][0], dp[N][1]) << endl;
}

F - Perils in Parallel

読んでさえいなかったんだけど難しかったらしい?

おわりに

AtCoderのレート最近連続して上がってたしまあ、下がることもあるよね
ただ、内容があんまりよくないのが駄目かなあ
Eみたいな問題初手DPで殴れるようにしたいね