ABC408個人的備忘録[A-E]

ORらないでバック地獄に堕ちた男の備忘録です

コンテスト概要

AtCoder Beginner Contest 408

開催日:2025年5月31日 21:00-22:40

A - Timeout

考察

寝ちゃったおじいちゃんのことを"Timeout"って言うの冷静に考えてやばいよね。

まぁ要するに最後に肩を叩いた時から、次に肩を叩くまでの時間がすべてS秒以内かどうかを判定すればOK。
最初が少々厄介。だが、とりあえず0秒に叩いたことにすれば引き算のみで判定できる。

100点と150点の違いって何だろうね？for文の有無なのかな？

提出

A.cpp

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

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

    int now = 0;// 0秒に肩を叩く
    string ans = "Yes";

    for(int i=0;i<t;i++){
        int x;
        cin >> x;

        if(x-now > s) ans = "No";//前と今回にS秒以上空いてたらNo
        now = x;
    }

    cout << ans << endl;
}

B - Compression

考察

一回しか登場しないものを出力と勘違いして1分ロス。

正しくは「1回以上登場する数字」を「重複なしで」出力でした。問題文はよく読もう。
さて、どう解くか？いろんな値を重複なしで管理してくれるちょうどいいものがあれば話が早い。"set"君の出番ですね。

ということで値を片っ端からsetに突っ込んでしまえばほぼおしまい。sizeを出して、順に列挙すればOK。setは勝手に昇順にしてくれるのでほんとに入れるだけ。

200点と150点の違いって何だろうね。見当つかないや。

提出

B.cpp

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

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

    set<int>st;//setを用意
    for(int i=0;i<n;i++){
        int x;
        cin >> x;

        st.insert(x);//順に入れていく
    }

    cout << st.size() << endl;//setの要素数を出力
    for(auto x:st) cout << x << endl;//setに格納された値を順に出力
}

C - Not All Covered

考察

まずはどこが守られているかを考えたい。
例えばサンプル３を図示すると

       1 2 3 4 5  #...守られてる
       = = = = =　_...守られてない
     1 _ # # # # 
     2 # # # # #
     3 # # _ _ _
     4 _ # # # _
     5 _ # _ _ _
     6 _ _ _ _ #
     7 _ # # # _
     8 # # _ _ _
     9 _ # _ _ _
    10 _ # # _ _ 

問題は「守られていない壁を"１か所でも"つくるには大砲をいくつ破壊するか？」である。この時「すべての壁についてそこを守っている大砲をすべて破壊」すれば守られていない壁を作ることができる。破壊した数が最も少ないものが答えになる。

つまり問題を言い換えれば「その壁を守っている大砲が最も少ないところはどこか？」ということになる。もちろん、すべて見ていけば解決するが計算量はO(NM)である。

大砲には範囲があり、全ての壁について守られている回数を早く知りたい。こういう時はimos法が役に立つ、範囲の最初と最後をいじるだけで回数を管理することができる。

というわけでimos法を使い壁ごとの守られてる数を導く。その後その最小値を出せばOK。

提出

C.cpp

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

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

    vector<int>num (n+1,0);//壁ごとの守られている数を管理
    for(int i=0;i<m;i++){
        int l,r;
        cin >> l >> r;
        l--;

        //imos法で数を管理
        num[l]++;//左端に+１
        num[r]--;//右端の1つ先に-1
        //こう書けば後で左から順に更新することで[l,r]の範囲に1を足せる。
    }

    int ans = n+1;
    for(int i=0;i<n;i++){
        //左から順に更新
        if(i != 0) num[i] += num[i-1];//0に左はないのでスキップ
        ans = min(ans,num[i]);//最小値が答え
    }

    cout << ans << endl;
    
}

D - Flip to Gather

考察

条件を満たすパターンはいくつもあるように見える。が、結局のところ
[0を0個以上][1を0個以上][0を0個以上]という形にしかならない。
なのでこの形を全パターン見ていきたい。方針は各パターンの最小値なのでDPの使いどころ。
DP[i][j]:i番目まで見たとき遷移jになるために必要なコスト
として前から順にやっていく。

計算量が少々不安だが文字数は$2\times10^5$であることが保証されているので心配なし。

提出

D.cpp

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

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

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

        vector<vector<int>>dp (n+1,vector<int>(3,n+1));//dpは大きい値を初期値に
        dp[0][0] = 0;//0文字目は当然遷移0だしコストも0

        for(int i=0;i<n;i++){
            if(s[i] == '0'){
                //文字が0の場合、
                //遷移1の時に変換コストがかかる
                dp[i+1][0] = min(dp[i+1][0],dp[i][0]);
                dp[i+1][1] = min(dp[i+1][1],dp[i][0]+1);
                dp[i+1][1] = min(dp[i+1][1],dp[i][1]+1);
                dp[i+1][2] = min(dp[i+1][2],dp[i][1]);
                dp[i+1][2] = min(dp[i+1][2],dp[i][2]);
            }else{
                //文字が1の場合、
                //遷移0,遷移2の時に変換コストがかかる
                dp[i+1][0] = min(dp[i+1][0],dp[i][0]+1);
                dp[i+1][1] = min(dp[i+1][1],dp[i][0]);
                dp[i+1][1] = min(dp[i+1][1],dp[i][1]);
                dp[i+1][2] = min(dp[i+1][2],dp[i][1]+1);
                dp[i+1][2] = min(dp[i+1][2],dp[i][2]+1);
            }
        }

        //最後まで行ったとき各遷移の最小値が答え
        cout << min(dp[n][0],min(dp[n][1],dp[n][2])) << endl;   

    }
    
}

E - Minimum OR Path

考察

ORが注目を浴びる問題初めて見たかも。普段XORばっかだし。

当然ルートを巡ろうとすればTLEになることが必至なので、効率よく答えを導ける方針を探したい。というわけで答えに対して絞り込みをしていく。
まずはとりあえず値を決め打つ。そして、その値を二進数表記したときに1のある場所だけが1になっている辺だけを通るルートを探す。ルートがあれば答え候補になるという感じである。ルートはBFSを使えばすぐにわかる。

さて問題は「どうやって値を決め打つか？」。ここで上から順に考えていく。例えば$1111$はルートがあって$111$はルートがなかったとする。
この時、4番目のbitは立てておかないと頂点Nまでいけないということになる。つまり答えは$ 1???$となる。
逆に両方ルートがあるなら4番目のbitは絶対に必要なものではないとわかる。つまり答えは$0???$となる。

このように上から順番に見ていくことでそのbitが必要なのか、不必要なのかを判定できる。

なお、私はORの性質を完全に見誤ったせいでバグを量産。20分のタイムロスへ。

提出

E.cpp

#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>>path;

bool BFS(int c,int n){
    vector<bool>gone (n,false);
    gone[0] = true;

    //BFSで頂点０から頂点N-1まで向かえるか？
    queue<int>que;
    que.push(0);

    while(!que.empty()){
        int now = que.front();
        que.pop();

        for(auto[x,y]:path[now]){
                    if(!gone[x] && !(y&c)){//辺がC以外のbitを使っていたら通れない
                gone[x] = true;
                que.push(x); 
            }
        }
    }

    return gone[n-1];//行けたかどうかを返す
}

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

    path.resize(n,vector<pair<int,int>>(0));//つないでいる頂点と辺の数字を管理
    for(int i=0;i<m;i++){
        int x,y,c;
        cin >> x >> y >> c;
        x--,y--;

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

    int keep = 0;

    for(int i = 29;i >= 0;i--){
        //上から順に確認
        int c = keep + (1<<i) - 1;//i番目だけを使えなくしたときを知りたい
        int d = (1<<30) - 1;
        c = d-c;

        if(!BFS(c,n)){//i番目が必要なら答えに足しておく
            keep += (1<<i);
        }
    }    
    
    cout << keep << endl;    
}

F - Athletic

考察

残された時間は20分。queueとセグ木の合わせ技で行けると確信。
なお、焦りからセグ木がちゃんとかけずタイムオーバー。

ORでミスらなければ...

結果

ABCDE ５完　79:00

順位　1557位
パフォーマンス　1326

感想

久々の5完だが、6完が狙えただけに悔しい結果に。

にしても5月は調子が悪すぎた。脱却の兆しが見えただけでも良しとする。