ABC385個人的備忘録

初めまして。紫前燈太と申します。
Atcoderをはじめて3年ほどになるのですが、過去の思考をまとめておきたいと思い立ったので今週から備忘録を付けてみようと思います。

コンテスト概要

ユニークビジョンプログラミングコンテスト2024 クリスマス(ABC385)

開催日:2024年12月21日 21:00-22:40

A-Equally

実装過程

a,b,cの値を受けとり言われた通りに比べればいいのだがifの書き分けが面倒に思う。
なので、vectorで3つ数字を受け取りソート。
条件は言い換えれば「3つが同じ数字」or「(小さい2つの合計)=(大きい1つ)」だから、どちらかの条件に当てはまってるかを確認。

提出

A.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int>num (3);
    for(int i=0;i<3;i++) cin >> num[i];

    sort(num.begin(),num.end());

    if(num[0] == num[2]) cout << "Yes" << endl;//最初と最後が同じ数なら3つとも同じ数
    else if(num[0] + num[1] == num[2]) cout << "Yes" << endl;
    else cout << "No" << endl; 
}

B-Santa Claus1

実装過程

境界に壁があるので何も考えず「向かう先に壁があれば停止」というシンプルなコードで済む。
通過する家の数は通過済みの家があると厄介なので申し訳ないが爆破させていただき更地にする。

提出

B.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    int h,w,x,y;
    cin >> h >> w >> x >> y;
    x--,y--;

    map<char,pair<int,int>>mp; //移動方法のコマンドをまとめておく
    mp['U'] = {-1,0},mp['D'] = {1,0};
    mp['R'] = {0,1},mp['L'] = {0,-1};

    vector<vector<char>>ct (h,vector<char>(w));
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++) cin >> ct[i][j];
    }

    string s;
    cin >> s;

    int ans = 0;
    for(auto nxt:s){
        auto [a,b] = mp[nxt];//移動コマンドを読み込む
        if(ct[x+a][y+b] != '#') x+=a,y+=b;//向かう先が壁じゃないなら移動

        if(ct[x][y] == '@'){
            ct[x][y] = '.';//家に到達したら更地にする
            ans++;
        }
    }
    
    cout << x+1 << " " << y+1 << " " << ans << endl;    
}

C-Illuminate Buildings

実装過程

これ茶パフォなんですか...
とりあえず同じ高さのビルの位置をまとめたリストを確保する。そしてビルの高さごとに等差数列の最長の値を調べる。
と、言えば簡単だが、実装はTLE。
二分探査の回数を減らしたり、高さをvectorではなくsetで管理したりと小細工をすることで何とかAC。

提出

C.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    map<int,vector<int>>mp;
    set<int>st;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        st.insert(x-1);
        mp[x-1].push_back(i);
    }

    int ans = 1;//解答が少なくとも1以上であることは保証されている。
    for(auto x:st){
        auto vec = mp[x];
        if(vec.size() == 1) continue;//同じ高さのビルが1つなら無視
        int m = vec.size();

        for(int i=0;i<m;i++){
            for(int j=i+1;j<m;j++){
                int now = vec[j],dis = vec[j]-vec[i],che = 2;
                //2つのビルを選び公差を求めておく
                while(true){
                    now += dis;
                    auto x = lower_bound(vec.begin(),vec.end(),now);
                    //二分探査で次の距離を求める
                    if(x == vec.end()) break;
                    if(*x != now) break;
                    //距離が存在しないor公差が合わないなら打ち切り

                    che++;
                }
                ans = max(ans,che);
            }
        }
    }

    cout << ans << endl;    
}

D-Santa Claus2

実装過程

ざっくり言えばBの無制限版。
1マスずつ進むと制約的に最大$2×10^{14}$マス移動するので当然ダメ。
なので、一気に進んで一気に家を潰す必要がある。
例えば上下に進むときx座標は変わらないので、あるx座標における家のあるy座標のリストがあれば範囲内を一気に潰せる。左右もまた然り。
家の座標をそれぞれx座標、y座標に分解して管理しておく。

提出

D.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    int n,m;
    ll x,y;
    cin >> n >> m >> x >> y;

    map<ll,set<ll>>xst,yst;
    for(int i=0;i<n;i++){
        ll s,t;
        cin >> s >> t;
        xst[s].insert(t); //あるx座標におけるy座標のリスト
        yst[t].insert(s); //あるy座標におけるx座標のリスト
    }

    int ans = 0;
    for(int i=0;i<m;i++){
        char a;
        ll b;
        cin >> a >> b;

        if(a == 'U' || a == 'D'){
            ll s,t;
            if(a == 'U'){
                s = y;
                y += b;
                t = y;
            }else{
                t = y;
                y -= b;
                s = y;
            }//移動範囲のy座標の最小値をs、最大値をtにしておく

            while(xst[x].lower_bound(s) != xst[x].end()){
                s = *xst[x].lower_bound(s);
                //二分探査で次に家のある座標を探す
                
                if(s<=t){
                    ans++;
                    xst[x].erase(s);
                    yst[s].erase(x);
                    //両方のリストから家を削除
                }else break;//範囲外なら打ち切り
            }
        }
        if(a == 'L' || a == 'R'){
            ll s,t;
            if(a == 'L'){
                t = x;
                x -= b;
                s = x;
            }else{
                s = x;
                x += b;
                t = x;
            }//移動範囲のx座標の最小値をs、最大値をtにしておく

            while(yst[y].lower_bound(s) != yst[y].end()){
                s = *yst[y].lower_bound(s);
                //二分探査で次に家のある座標を探す
                if(s <= t){
                    ans++;
                    yst[y].erase(s);
                    xst[s].erase(y);
                    //両方のリストから家を削除
                }else break;//範囲外なら打ち切り
            }
        }        
    }

    cout << x << " " << y << " " << ans << endl;
}

E-Snowflake Tree

実装過程

見た目からして難しそうな雰囲気が漂うが、よくよく見れば「ユ木」は3層しかない。
なのでそれぞれ中心を決め打ち下2層をうまく選び「ユ木」の最大値を考えればいい。
2層目の頂点の要素数をN個とすると、1つが中心に向いてるので葉の最大値はN-1個となる。
「ユ木」の葉は「(葉がM個以上ついてるもの)×M」なので葉を1から順に調べて足し上げれば「ユ木」の最大値が求まる。
ただ、調べたいのは消す頂点の最大値なので、出力の時は全体から最大値を引く。

提出

E.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<vector<int>>num (n,vector<int>(0));
    for(int i=0;i<n-1;i++){
        int x,y;
        cin >> x >> y;
        num[x-1].push_back(y-1);
        num[y-1].push_back(x-1);
    }

    int ans = n;
    for(auto x:num){
        set<int>st;
        map<int,int>mp;
        int now = 0;
        for(auto y:x){
            int z = num[y].size();
            if(z == 1) continue;
            //葉がないなら無視
            now++;
            mp[z-1]++;
            st.insert(z-1);
        }
        
        int siz = 0;
        for(auto y:st){
            siz = max(siz,1+now+y*now);
            //「ユ木」の大きさは「中心+2層目の数+葉の数」
            //そして「葉の数」は「2層目の数×それぞれの葉の数」
            now -= mp[y];
        }

        ans = min(ans,n-siz);
    }

    cout << ans << endl;
}

結果

バーチャル参加
結果　ABC(2)D(1)E　5完 109:56

順位(参考)　1210位相当
パフォーマンス(参考)　1449相当

感想

100分台の5完なので振るわない結果かと思ったら、5完の最下位ですら1268位となかなかに難しい回だった。
CとDで迷走したため下手したら2完になるのではないかという恐怖とずっと戦っていた。

個人的難易度
A < B < E < D < C