ABC378振り返り

コンテスト総評

Dまでそこそこ早く解けて緑中位パフォ取れ、かなり良き結果でした！ただコンテスト中にEでなくFを真剣にやっていればレートさらに爆上げの"可能性"もあったのでちょっと複雑...まぁEの方がFより解けた人数多いししょうがない。
問題はA~Dの全ての問題が易しめで典型要素が多いなぁと思った。

A - Pairing(diff22)

mapで各色のボールの個数を管理します。各色の個数をxとしたときに捨てる操作をできる回数は$\lbrack \frac{x}{2} \rbrack$回（切り捨て除算)。それを各色で求めた総和を出力しました。多分もっと簡単なやり方がいっぱいあります。

int main(){
    vector<int> a(4);
    rep(i,4)cin >> a[i];
    map<int,int> mp;
    rep(i,4){
        mp[a[i]]++;
    }
    int ans = 0;
    for(auto p : mp){
        ans += p.second/2;
    }
    cout << ans << endl;
}

B - Garbage Collection(diff118)

Bのくせに難しい...
$d$日に種類$t$のゴミが出た時に日付$q$で割ったあまりが$r$の日にゴミが収集される時
①$d$ $mod$ $q$ $=$ $r$
②$d$ $mod$ $q$ $<$ $r$
③$d$ $mod$ $q$ $>$ $r$
の3通りで場合分けしました。
①の時は次に収集される日はdでおk
②の時は次に収集されるのは$d$日目から$r$ $-$ $d$ $mod$ $q$日進んだ日
③の時は次に収集されるのは$d$日目から$q$ $-$ $d$ $mod$ $q$ $+$ $r$日進んだ日
汚いですがこの場合分けと式で多分正しい答えが出てます

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vi q(n),r(n);
    rep(i,n){
        cin >> q[i] >> r[i];
    }
    int Q;
    cin >> Q;
    rep(i,Q){
        int t,d;
        cin >> t >> d;
        t--;
        if(d%q[t] == r[t]){
          cout << d << endl;
        }
        else if(d%q[t] > r[t]){
            cout << d+q[t]-d%q[t]+r[t] << endl;
        }
        else{
            cout << d-d%q[t]+r[t] << endl;
        }

    }
}

C - Repeating(191)

i番目まで見ていてそれより前に$a_i$が出現している時の最大の添え字を求めるこの問題ではmapが使えそうです。i番目まで見た時にmapに$a_i$がkeyとなるものがなければ-1を出力、そうでなければmapの$a_i$の値を出力します

int main(){
    int n;
    cin >> n;
    vl a(n);
    rep(i,n){
        cin >> a[i];
    }
    map<ll,ll> mp;
    vl b(n);
    rep(i,n){
        if(mp.count(a[i])){
            b[i] = mp[a[i]];
        }
        else{
            b[i] = -1;
        }
        mp[a[i]] = i+1;
    }
    rep(i,n){
        cout << b[i] << " ";
    }
    cout << endl;
}

D - Count Simple Paths(diff587)

制約から漂う再帰の雰囲気...実装問題です
再帰関数にsetを持たせて、通ったマスを管理しました

vl di = {1,0,-1,0};//下、左、上、右
vl dj = {0,-1,0,1};


ll h,w,k;
vector<vector<char>> s(h,vector<char>(w));

ll f(int i,int j,int K,set<P>& st){
    if(K == k)return 1;
    ll now = 0;
    for(int d = 0;d < 4;d++){
        if(st.count(make_pair(i+di[d],j+dj[d])))continue;
        if(out_grid(i+di[d],j+dj[d],h,w))continue;
        if(s[i+di[d]][j+dj[d]] == '#')continue;
        st.insert(make_pair(i+di[d],j+dj[d]));
        now += f(i+di[d],j+dj[d],K+1,st);
        st.erase(make_pair(i+di[d],j+dj[d]));
    }
    return now;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> h >> w >> k;
    s.resize(h,vector<char>(w));
    rep(i,h){
        rep(j,w){
            cin >> s[i][j];
        }
    }

    ll ans = 0;
    rep(i,h){
        rep(j,w){
            if(s[i][j] == '#')continue;
            set<P> st;
            st.insert(make_pair(i,j));
            ans += f(i,j,0,st);
        }
    }

    cout << ans << endl;
}

F - Add One Edge 2(diff1436) upsolve

Xで見た解法が自分がコンテスト中に問題をチラリと見た時に思いついたものとほぼ同じだったのでやってみたら解けました。やることとしては次数3の頂点からBFSで次数3の頂点のみの連結成分を列挙し、各連結成分で繋がっている次数2の頂点数を求めて張れる辺の数の通りを数え上げます。木DPを完全に忘れたので復習しときます...

int main(){
    ll n;
    cin >> n;
    ll ans = 0;
    vvl g(n);
    rep(i,n-1){
        int u,v;
        cin >> u >> v;
        u--;v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    set<ll> deg3;
    for(int i = 0;i < n;i++){
        if(g[i].size() == 3)deg3.insert(i);
    }
    while(!deg3.empty()){
        set<ll> st;
        queue<ll> q;
        q.push(*deg3.begin());seen[*deg3.begin()];
        deg3.erase(*deg3.begin());
        while(!q.empty()){
            ll v = q.front();q.pop();
            st.insert(v);
            for(ll nv : g[v]){
                if(g[nv].size() == 3 && deg3.count(nv)){
                    q.push(nv);
                    deg3.erase(nv);
                }
            }
        }

        ll cnt2 = 0;
        for(auto x : st){
            for(ll u : g[x]){
                if(g[u].size() == 2){
                    cnt2++;
                }
            }
        }
        ans += (cnt2-1)*cnt2/2;
    }
    cout << ans << endl;
}