AtCoder Beginner Contest 173 ABC173 参加記

24分4完水パフォでした。少しhighestを更新しましたが、Eの実装で凡ミスしていて悲しくなりました。

• 私の提出へのリンク

A - Payment

問題へのリンク

解説

です。切り上げを覚えてしまいましょう。

実装

int main() {
    ll N;
    cin >> N;
    ll cnt = (N + 1000 - 1) / 1000;
    cout << 1000 * cnt - N << endl;
}

B - Judge Status Summary

問題へのリンク

解説

C++ならmap、Pythonならdictionaryを使って書きましょう。

実装

int main() {
    int N;
    cin >> N;
    map<string,ll> mp;
    rep(i,N){
        string S;
        cin >> S;
        mp[S]++;
    }
    string tmp[] = {"AC","WA","TLE","RE"};
    for(auto &s: tmp){
        cout << s << " x " << mp[s] << endl;
    }
}

C - H and V

問題へのリンク

解説

いわゆるbit全探索です。 でできます。

実装

check関数を別で書くと見通しが良い気がします。

int main() {
    ll H, W, K;
    cin >> H >> W >> K;
    vector<string> c(H);
    rep(i,H)cin >> c[i];
    auto check = [&](ll s, ll t){
        set<pair<int,int>> st;
        rep(i,H){
            if(!(bit(i) & s)){
                rep(j,W){
                    if(bit(j) & t)continue;
                    if(c[i][j] == '#')st.insert(make_pair(i,j));
                }
            }
        }
        rep(j,W){
            if(!(bit(j) & t)){
                rep(i,H){
                    if(bit(i) & s)continue;
                    if(c[i][j] == '#')st.insert(make_pair(i,j));
                }
            }
        }
        return st.size() == K;
    };
    ll ans = 0;
    for(ll x = 0; x < bit(H); x++){
        for(ll y = 0; y < bit(W); y++){
            if(check(x, y))ans++;
        }
    }
    cout << ans << endl;
}

D - Chat in a Circle

問題へのリンク

解説

小さいパターンでやってみると最大の場合以外は二回カウントできそうなので、大きい方から貪欲です。証明は難しそうです。

実装

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N)cin >> A[i];
    sort(all(A));
    reverse(all(A));
    vector<ll> v;
    v.push_back(A[0]);
    rep1(i,N){
        v.push_back(A[i]);
        v.push_back(A[i]);
    }
    cout << accumulate(v.begin(), v.begin() + N - 1, 0LL) << endl;
}

E - Multiplication 4

記事を分けました

coonevo.hatenablog.com

F - Intervals on Tree

問題へのリンク

まだやっていません。

-> 20200707追記

復習したので記事を書きました。

coonevo.hatenablog.com