ABC409個人的備忘録[A-E](Fもある)

=に泣かされた男の備忘録です

コンテスト概要

AtCoder Beginner Contest 409

開催日:2025年6月7日 21:00-22:40

A - Conflict

考察

前から順に見て行って高橋君、青木君がともにoを選んでいる場所があればYes、そうでなければNo。

文字の長さは提示されているので若干手間が省ける。

提出

A.cpp

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

int main(){
    int n;
    string s,t;
    cin >> n >> s >> t;

    string ans  = "No";//Noで初期化
    for(int i=0;i<n;i++){
        //i番目がともにoなら答えはYes
        if(s[i] == 'o' && t[i] == 'o') ans  = "Yes";
    }

    cout << ans << endl;
}

B - Citation

考察

B問題なので正直何とでもなる。
とりあえず配列を受け取り「0以上は0個以上か？」「1以上は1個以上か？」を順に見ていき成り立たなかったらその前の数が答え。$O(N^2)$だがNは100以下なので余裕。これが簡単で、安全な方法。

自分はimos法で実装。数字はＮ個しかないので「N+1以上はN+1個以上か？」の答えはもちろんNoになる。なので100の配列を用意して0~Niをimos法で足していく。その後順に「i以上はi個以上か？」を確かめればOK。

なお制約の$10^9$を見落としRE。制約はちゃんと読もうね。

提出

B.cpp

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

int main(){
    int n;

    cin >> n;

    vector<int>num (101,0);//答えは100以下なので100まで確認すればOK
    for(int i=0;i<n;i++){
        int x;
        cin >> x;

        //0~Xまでに１を足していく
        num[0]++;
        if(x+1 < 101)num[x+1]--;//100を超えてるなら調節不要
    }
    
    int ans  = 0;
    for(int i=1;i<101;i++){
        num[i] += num[i-1];
        if(num[i] >= i) ans  = i;//iがi個以上あるなら答えの可能性あり。
    }

    cout << ans << endl;    
}

C - Equilateral Triangle

考察

ややこしく見えるが単純な問題。
要するに選んだ三点がすべて$L/3$離れている組み合わせはいくつか？ということ。
なのでそれぞれの頂点番号には興味がなく円周のどの場所に点がいくつあるかだけわかればいい。
また$L \leq 3 \times 10^5 $なので全部の頂点を管理できる。

というわけでとりあえず$N_1$を距離0としてここから時計回りに進んだ距離だけを見ていく。それぞれの距離はLで割った余りがそのまま対応する。

そして距離０から距離iからそれぞれi+$L/3$,i+$2L/3$離れた場所にある点から1つずつ選べばいい。もちろん$L/3$は整数である必要があるのでLが三の倍数でなければ当然答えは０。

で、個数だがそれはシンプルにそれぞれを掛け算すればいい。

提出

C.cpp

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

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

    //Lが3の倍数でなければ論外
    if(l%3 != 0){
        cout << "0" << endl;
        return 0;
    }

    int now  = 0;
    vector<ll>len (l,0);//N1を0とした時の時計回りの距離を管理
    len[0]++;
    for(int i=1;i<n;i++){
        int x;
        cin >> x;

        now += x;
        now %= l;//行き過ぎてもLで割れば、余りが距離になる

        len[now]++;
    }

    ll ans  = 0;
    ll m = l/3;
    for(int i=0;i<m;i++){//調べる範囲はL/3で十分
        ans += len[i]*len[i+m]*len[i+2*m];//3か所それぞれの数を掛け算
    }

    cout << ans << endl;
}

D - String Rotation

考察

まず、操作が何回でもできると思い大幅なタイムロス。

もちろん文字列はそれなりの長さがあるので全パターン試す余裕はない。なので効率よくシフトさせる場所を知りたい。
ここで、そもそもシフトさせるとどんな変化があるのかをしっかり考察する。
例えば[AB****]となっている文字列をシフトさせると[B****A]となる。要するにシフトさせる場所の「次の文字」がそこにくることになる。
ということは次の文字がアルファベット順で手前の文字でない限りシフトさせるメリットはなさそう。
また、更新ポイントが2か所ある場合、後ろの更新より前の更新のほうがより早くなる。だから、前から順に見ていき次の文字が小さいところを更新の先頭にすればいい。

さて次に更新ポイントの文字をどこに差し込むか？
[DABCXYZ]という文字列の場合、更新ポイントは先頭のDである。このDを[ABCXYZ]のどこに入れるかだが、辞書順を更新できるのは「入れたいアルファベットよりも後のアルファベットの前」だけである。
例えば[DABX]は[ADBX],[ABDX],[ABXD]の3パターンの更新ができるが、もとより早いのは[ABDX]である。要するに「入れたいアルファベットよりも後のアルファベットの前」で一番早い場所に入れればいい。

最後、操作を必ず１回するという点だが、部分文字列を１にすることで変化させないという選択肢もとれるのでもともと最良の場合でも問題ない。

これを実装すればよいのだが$\leq$ と $<$を間違え4ペナ＆50分のロス。
最悪でしかない。

提出

A.cpp

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

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

    for(int i=0;i<n;i++){
        int len;
        string s;
        cin >> len >> s;

        vector<vector<int>>pos(26,vector<int>(0));
        //文字を早く見つけたいのでそれぞれの文字の出現位置を管理

        for(int j=0;j<len;j++) pos[s[j] - 'a'].push_back(j);
        for(int j=0;j<26;j++) pos[j].push_back(len);

        for(int j=0;j<len-1;j++){
            if(s[j] <= s[j+1]) continue;//右がデカくないならスキップ
            int k =  s[j] - 'a';

            int p = len;
            for(int l=k+1;l<26;l++){
                int x = *lower_bound(pos[l].begin(),pos[l].end(),j);
                p = min(p,x);
                //後のアルファベットが最初に出る場所を確認
                //ないなら一番後ろに行ってもらう
            }

            s.insert(s.begin()+p,s[j]);//場所pに文字を差し込む
            s.erase(s.begin()+j);//元あった文字を削除
            break;
        }

        cout << s << endl;
    }
    
}

E - Pair Annihilation

考察

Dが上手くいかなかったので先にE問題

陽電子と電子がややこしいのでひっくるめて粒子と呼ぶ
できる限りコストの大きいところに粒子を通したくない。いろいろな方法を試すが、どうあがいても一定数通さざるえないことが判明する。

ある辺が頂点U，Vをつないでいるとする。この時$X_i$の合計は0なので、Ｕ側の残粒子の数と、Ｖ側の残る粒子の数は同じになる。ということはこの辺は残った粒子をU→Vにせよ、U←Vにせよ通さないといけない。

ということはあまり工夫の仕様がなく、愚直に陽電子と電子を運び消すしかない。

というわけで頂点１(正直どこでもかわらない)を根とする木を作り葉のほうから順に上へと上げるしかない。

これはDFSを使えば瞬殺。

コードの正当性を証明するのが難しいね。

提出

E.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<pair<int,ll>>>path;
vector<ll>now;
vector<bool>gone;

ll DFS(int n){
    gone[n] = true;//すでに見たならマーク

    ll ans = 0;
    for(auto [x,c]:path[n]){
        if(gone[x]) continue;//行ったことある場所はスキップ

        ans += DFS(x) + abs(now[x])*c;
        //これまでの合計に粒子を動かすコストを足す
        now[n] += now[x];//粒子を合成(同じなら足し、違うなら消滅)
    }

    return ans;
}

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

    path.resize(n,vector<pair<int,ll>>(0));
    now.resize(n);
    for(int i=0;i<n;i++) cin >> now[i];//粒子をメモ
    for(int i=0;i<n-1;i++){//コスト込みでそれぞれの辺の情報を記録
        int x,y;
        ll c;
        cin >> x >> y >> c;
        x--,y--;

        path[x].push_back({y,c});
        path[y].push_back({x,c});
    }

    gone.resize(n,false);

    cout << DFS(0) << endl;//DFSにあとはお任せ
    
}

F - Connecting Points

考察

完全な時間切れですが、思ったことをやったらACしやがったので書き記す。

頂点数は高々3000しかなくそのペアも$10^7$以下。なので距離に関してはもう全通り試すのが正義。
距離に関しては45度回すやつを使えばなんてことはない。

まず初期メンバーに対して距離を出し、priority_queueに突っ込む。このときpriority_queueは距離が小さい順に並ぶように改造しておく。

連結に関してはUnionFindが勝手にやってくれる。頂点数は増えていくのが厄介に見えるがどうせ頂点数は高々3000なのであらかじめ3000で作っておく。

クエリ1の時
新しい座標を管理しつつ、すべてと頂点との距離を割り出し、priority_queue突っ込む。

クエリ2の時
あらかじめUnionFindで連結個数を管理しておく。すべて連結ならー１を出力。
priority_queueから長さの短い順に取り出す。頂点同士が連結ならスキップ。連結でないなら長さをメモし、連結させる。
後は同じ長さのものを取り出しつづけジャンジャン連結。
最後に長さを出力。

クリエ3の時
UnionFindに聞くだけ

これを実装すればいいだけ。大変なんだけどね。40分程度でAC。
全部D問題のせいだ。

提出

F.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T> using p_que = priority_queue<T,vector<T>,greater<T>>;

//45度回す構造体
struct Mdis{
    ll u,v;

    Mdis(ll x,ll y){
        //45度回すのは足し算と引き算で事足りる
        u = x+y;
        v = x-y;
    }

    ll dist(Mdis const &m){
        //距離を求める関数
        //差の絶対値が大きいほうが距離
        //詳しくは貼った記事を見て
        return max(abs(u - m.u),abs(v - m.v));
    }
};

//長さとその頂点を管理する構造体
struct Len{
    ll len;
    int x,y;

    Len(ll l,int xx,int yy):len(l),x(xx),y(yy){};
};

//普通のUnionFind
struct UnionFind{
    vector<int>par;
    int cnc;
    //連結した回数を管理
    //これが頂点数と同じなら全部連結。    

    UnionFind(int n):par(n){
        for(int i=0;i<n;i++) par[i] = i;
        cnc = 1;//最初は１
    }

    int root(int n){//親番号を返すやつ
        if(par[n] == n) return n;
        return par[n] = root(par[n]);
    }

    void unite(int n,int m){//くっつけるやつ
        int rn = root(n),rm = root(m);
        if(rn == rm) return;

        par[rn] = rm;
        cnc++;
    }

    bool same(int n,int m){//連結か確認するやつ
        int rn = root(n),rm = root(m);

        if(rn == rm) return true;
        return false;
    }
};

//構造体同士の大小を比べるやつ１
bool operator<(const Len &n,const Len &m){
    if(n.len == m.len){
        if(n.x == m.x) return n.y < m.y;
        return n.x < m.x;
    }
    return n.len < m.len;
}

//構造体同士の大小を比べるやつ２
bool operator>(const Len &n,const Len &m){
    if(n.len == m.len){
        if(n.x == m.x) return n.y > m.y;
        return n.x > m.x;
    }
    return n.len > m.len;
}


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

    vector<Mdis>pos;
    for(int i=0;i<n;i++){
        ll x,y;
        cin >> x >> y;

        pos.emplace_back(x,y);//45度回して管理
    }

    p_que<Len>que;
    for(int i=0;i<n;i++){//全ペアの距離を出しqueに入れる
        for(int j=1;j<n;j++){
            Len l(0,i,j);
            
            l.len = pos[i].dist(pos[j]);
            que.push(l);
        }
    }

    UnionFind tree(3000);//多めに3000作っておく
    int m = n;
    for(int i=0;i<q;i++){
        int c;
        cin >> c;

        if(c == 1){
            ll x,y;
            cin >> x >> y;

            pos.emplace_back(x,y);//新人を追加
            for(int j=0;j<m;j++){//新人との距離をすべて出す
                Len l(0,j,m);
                l.len = pos[j].dist(pos[m]);
                
                que.push(l);
            }
            m++;
        }
        if(c == 2){
            if(tree.cnc == m){//全連結なら-1
                cout << "-1" << endl;
            }else{
                ll now = (1LL<<60);
                while(!que.empty()){
                    if(que.top().len > now) break;//定めた長さより大きいならおしまい
                    auto[len,x,y] = que.top();
                    que.pop();

                    if(tree.same(x,y)) continue;//もう連結ならスキップ
                    now = len;//長さを定める
                    tree.unite(x,y);//くっつける
                }

                cout << now << endl;
            }
        }

        if(c == 3){
            int x,y;
            cin >> x >> y;
            x--,y--;

            //同じか聞く
            if(tree.same(x,y)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}

結果

AB(1)CD(4)E 5完　123:35

順位　2697位

パフォーマンス　1068

レート　1274(-21)

感想

そうですね。明らかにスピードが足りませんね。
そうですね。明らかにケアレスミスが多いですね。

精進すれど遅いなら意味がない。どうしたら早くなるんだろう？