AtCoder Beginner Contest 173 感想 - スコルの知恵袋

問題

感想

4完。冷えstreak2です。

青の方々とはやっぱり実力の差を感じるし、今まではレートが上振れしてただけで、それが元に戻ってきているのだろう（かなしい）。

A - Payment

提出コード

void solve() {
    ll N;
    cin >> N;
    N %= 1000;
    if (N == 0) {
        N = 1000;
    }
    cout << 1000 - N << "\n";
}

B - Judge Status Summary

提出コード

void solve() {
    ll N;
    cin >> N;
    Vl num(4);
    string s[] = {"AC", "WA", "TLE", "RE"};
    for (ll i = 0; i < N; i++) {
        string t;
        cin >> t;
        for (ll j = 0; j < 4; j++) {
            if (s[j] == t) {
                ++num[j];
            }
        }
    }
 
    for (ll i = 0; i < 4; i++) {
        cout << s[i] << " x " << num[i] << "\n";
    }
}

C - H and V

最初？？ってなったけど、制約が「bit全探索しろ」と言っていたので事なきを得た。

提出コード

void solve() {
    ll H, W, K;
    cin >> H >> W >> K;
    int cell[7][7];
    for (ll i = 0; i < H; i++) {
        string s;
        cin >> s;
        for (ll j = 0; j < W; j++) {
            cell[i][j] = s[j] == '#' ? 1 : 0;
        }
    }
 
    ll ans = 0;
    for (ll mask1 = 0; mask1 < (1ll << H); mask1++) {
        for (ll mask2 = 0; mask2 < (1ll << W); mask2++) {
            ll cnt = 0;
            for (ll i = 0; i < H; i++) {
                if (!((mask1 >> i) & 1)) continue;
                for (ll j = 0; j < W; j++) {
                    if (!((mask2 >> j) & 1)) continue;
                    if (cell[i][j] == 1) {
                        ++cnt;
                    }
                }
            }
            if (cnt == K) {
                ++ans;
            }
        }
    }
 
    cout << ans << "\n";
}

D - Chat in a Circle

$A_i$ が大きなものから動かし、最も心地よさが大きくなる位置に割り込ませれば良いという直感を信じた。

実装では、mapで「心地よさが $k$ となる割り込ませ先の数」を管理して上の操作を実現した。

ここでしょうもないミスで1WAしたの痛かったなぁ。

提出コード

void solve() {
    ll N;
    cin >> N;
    Vl A(N);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end(), greater<ll>());
 
    ll ans = A[0];
    map<ll, ll> mp;
    mp[A[1]] = 2;
    for (ll i = 2; i < N; i++) {
        auto itr = mp.rbegin();
        auto [kn, val] = *itr;
        ans += kn;
        --val;
        if (val == 0) {
            mp.erase(kn);
        }
        else {
            mp[kn] = val;
        }
        mp[A[i]] += 2;
    }
 
    cout << ans << "\n";
}

E - Multiplication 4

はっきり言って手も足もでなかった。解説PDFを見るとふんふんとはなるんだけど、これを思いつくのは今の僕にはしんどそうだ。

こういう注意深く場合分けして解く問題、どうやったら解けるようになるんだろう......。競プロ始めてから1年以上経つけどずっと苦手なままだ。

コンテスト後提出コード(解説AC)

// ModInt 略

constexpr ll MOD = 1e9 + 7;
using Mint = ModInt<MOD>;
 
void solve() {
    ll N, K;
    cin >> N >> K;
    Vl P, Q;
    for (ll i = 0; i < N; i++) {
        ll a;
        cin >> a;
        if (a >= 0) {
            P.emplace_back(a);
        }
        else {
            Q.emplace_back(a);
        }
    }
    sort(P.begin(), P.end(), greater<ll>());
    sort(Q.begin(), Q.end());
 
    ll np = (ll)P.size();
    ll nq = (ll)Q.size();
 
    Mint ans;
 
    if (N == K) {
        ans = 1;
        for (ll i = 0; i < np; i++) {
            ans *= P[i];
        }
        for (ll i = 0; i < nq; i++) {
            ans *= Q[i];
        }
    }
    else if (K % 2 == 1 && np == 0) {
        ans = 1;
        for (ll i = 0; i < K; i++) {
            ans *= Q[nq - 1 - i];
        }
    }
    else {
        ans = 1;
        ll idx1 = 0, idx2 = 0;
        while (idx1 + idx2 < K) {
            if (idx1 < np && idx2 < nq) {
                if (P[idx1] >= -Q[idx2]) {
                    ans *= P[idx1++];
                }
                else {
                    ans *= Q[idx2++];
                }
            }
            else if (idx1 < np) {
                ans *= P[idx1++];
            }
            else {
                ans *= Q[idx2++];
            }
        }
 
        if (idx2 % 2 == 1) {
            if (idx1 >= 1 && idx1 < np && idx2 >= 1 && idx2 < nq) {
                ll t1, t2;
                t1 = P[idx1 - 1] * P[idx1];
                t2 = Q[idx2 - 1] * Q[idx2];
                if (t1 >= t2) {
                    ans *= P[idx1];
                    ans /= Q[idx2 - 1];
                }
                else {
                    ans *= Q[idx2];
                    ans /= P[idx1 - 1];
                }
            }
            else if (idx1 >= 1 && idx2 < nq) {
                ans *= Q[idx2];
                ans /= P[idx1 - 1];
            }
            else {
                ans *= P[idx1];
                ans /= Q[idx2 - 1];
            }
        }
    }
 
    cout << ans << "\n";
}

F - Intervals on Tree

解けなかった。以下、コンテスト後の考察。

森の連結成分の個数は (頂点数) - (辺数) に等しいということがキー。これコンテスト中に気づけるかな～～。森から辺を一つ奪うと連結成分数が1つ増えるということにさえ気がつけば何とかなるかも。

f の値は (部分グラフの頂点数) - (部分グラフの辺数) だから、各頂点や辺が答えにどれくらい寄与するかを考えればいい。

全頂点の寄与の総和は、区間の幅が1のとき、2のとき、...... と考えることで $1 \cdot N + 2 \cdot (N - 1)+ \cdots + N \cdot 1$ だと分かる。

また、辺 (u, v) (u < v) の寄与は、この辺が区間を全列挙したときに何回登場するかを考えることで $u (N - v + 1)$ だと分かる。

結局、答えは、

$\displaystyle{ ans = \sum_{k=1}^N k (N-k+1) - \sum_{k=1}^{N-1} u_k (N - v_k + 1) }$

これは $O(N)$ で求められる。入力が $u_k > v_k$ ならばswapしなければならないことに注意。

コンテスト後提出コード

void solve() {
    ll N;
    cin >> N;
    ll ans = N * (N + 1) * (N + 1) / 2 - N * (N + 1) * (N * 2 + 1) / 6;
    for (ll i = 0; i < N - 1; i++) {
        ll u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        ans -= u * (N - v + 1);
    }
    cout << ans << "\n";
}