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

問題を咀嚼する時間が長い男の備忘録です

コンテスト概要

AtCoder Beginner Contest 401

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

A - Status Code

考察

HTTPステータスコードを題材？にした問題。
さすがに「問題文通りにする」以外の解説がない。
しいて言うなら英語の綴りに注意。

提出

A.cpp

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

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

    //nが200以上300未満かの確認
    if(n < 300 && n >= 200) cout << "Success" << endl;
    else cout << "Failure" << endl;
}

B - Unauthorized

考察

HTTPステータスコード2問目。401 Unauthorized(認証が必要)
いろんな文字列が出てきているが要するに、
「現在のログイン状況が"logout"」の時に「"private"にアクセス」した回数
が答え。

ログインを管理するフラグを持っておけば後は数えるだけ。

提出

B.cpp

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

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

    //現在のログイン状況を確認。
    string s = "logout";

    int ans = 0;
    for(int i=0;i<n;i++){
        string str;
        cin >> str;

        //操作がloginかlogoutならフラグを変更
        if(str[0] == 'l') s = str;
        else{
            //logout時にprivateに来たらカウントを増やす。
            if(str == "private" && s == "logout") ans++;
        }
    }

    cout  << ans << endl;
}

C - K-bonacci

考察

前K項の和で定義される拡張版フィボナッチ数。
(K-1)項目までは１と定義されているのでK>Nの時、第N項目はもちろん１。
そうでない場合を考えたい。

第K項目は前K個の和であり、それらはすべて１なので値はKになる。
第(K+1)項目も前K個の和、すなわち第1項目から第K項目の和である。
これは（第０項目から第K項目までの和）-（第0項目の値）+（第K項目の値）で求められる。
これを一般化すればドミノ式に求まりそう。

第M項目について前K項の和をSとする。
この時の第(M＋1)項目の値は S - [第{M+1-(K+1)}項目の値] + [第M項目の値]となる。

少しややこしいが要するにK個の和をもって置き、都度更新を第N項目までやればOK。
あ、後余りを求めるのを忘れないよう。

提出

C.cpp

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

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

    //Nが小さいなら値は１
    if(n < k){
        cout << "1" << endl;
        return 0;
    }

    //数列の第K-1項目までは１
    vector<ll>num (k,1);
    //前ｋ個の合計を持っておく
    ll now = k;

    for(int i=k;i<=n;i++){
        //第i項目は前Ｋ個の合計
        num.push_back(now);

        //合計からK+1項前を引き、1項前を足す。
        now += num[i];
        //c++の場合引き算の余りに注意
        now += lim - num[i-k];
        //余りを出す
        now %= lim;
    }

    cout << num[n] << endl;
}

D - Logical Filling

考察

出力例が意味不明で当惑した問題。
順番に冷静に処理する必要があった。

まず与えられる文字列について、矛盾すること(そもそもoが連続する)はないのでoの前後に・(本来はピリオド)おいておく。
また文字列に含まれるoの数をKとする。

その後連続する？の数に注目する。？がＮ個連続するとき2つに1つはoを置けるので最大$\lceil N/2\rceil$(半分の切り上げ)個のoを置くことになる。この数の合計をSとする。

KとSの合計がMより小さいとき、なんでもありになるので？はそのまま出力。
Mと同じとき、できるだけ詰めてoを入れなければならない。？が奇数個連続するときo.o.o.oとoから始めて交互に置くしかない。
一方偶数の時は.o.oまたはo.o.と2通りの置き方ができる。つまり？が偶数連続するときは？のまま、そうでないならoから始めて交互に置く。

これを実装できればOK。
ごり押しだなぁと思ったが解説通りでびっくり。

提出

D.cpp

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

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

    //一旦?で初期化
    vector<char>num (n,'?');
    for(int i=0;i<n;i++){
        char x;
        cin >> x;

        if(x != '?'){
            //?ではないなら文字を確定させる
            num[i] = x;
            if(x == 'o'){
                //oの時前後は.で確定
                if(i != n-1) num[i+1] = '.';
                if(i != 0) num[i-1] = '.';
                //使えるoの数を減らしておく
                m--;
            }
        }
    }
    //使えるoがないならあとは全部.
    if(m==0){
        for(auto x:num){
            if(x=='?') cout << '.';
            else cout << x;
        }
        return 0;
    }

    //前から順に?の連続数を確認
    queue<int>que;

    //便宜上後ろにダミーを置いておく
    num.push_back('.');
    int cnt = 0;
    int sum = 0;
    for(int i=0;i<=n;i++){
        //?が連続するならカウントを増やす
        if(num[i] == '?') cnt++;
        else if(cnt != 0){
            //カウントが途切れる場合値をqueueに入れてカウント初期化
            que.push(cnt);
            sum += (cnt+1)/2;
            cnt = 0;
        }
    }

    //ダミー消去
    num.pop_back();

    //おけるoが少ないなら?をそのまま出力
    if(sum != m){
        for(auto x:num) cout << x;
        cout << endl;

        return 0;
    }

    for(int i=0;i<n;i++){
        if(num[i] != '?'){
          cout << num[i];
          continue;
        } 
        int k = que.front();
        que.pop();
        i += k-1;

        for(int j=0;j<k;j++){
            //？の連続する数で分岐
            if(k%2 == 0) cout << '?';
            else if(j%2 == 0) cout << 'o';
            else cout << '.';
        }
    }
    cout << endl;
}

E - Reachable Set

考察

説明しづらい問題が続く
とりあえず頂点１から順番に頂点を増やしていく。
この時頂点KとつながっていてかつKより大きい値は邪魔な頂点になる。言い換えれば頂点１から頂点Kまでと連結しているKより大きい頂点の数が答えとなる。これはsetとかを使えば一撃。

次に問題なのが果たして頂点1から頂点Kまでがすべて連結かどうかに関してはUnionFindに頼ればOK。

提出

E.cpp

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

//基本的なUnionFind
struct UnionFind{
    vector<int>par;
    vector<int>siz;

    UnionFind(int n):par(n),siz(n,1){
        for(int i=0;i<n;i++)par[i] = i;
    }

    int root(int n){
        if(n == par[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[rm] = rn;
        //サイズも管理
        siz[rn] += siz[rm];
    }
};


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

    vector<set<int>>path (n+1);
    for(int i=0;i<m;i++){
        int x,y;
        cin >> x >> y;

        path[x].insert(y);
        path[y].insert(x);
    }

    //邪魔な頂点の管理用
    set<int>bin;
    UnionFind uf(n+1);
    //頂点１に関して周り全てが邪魔である。
    for(auto x:path[1])bin.insert(x);
    cout << bin.size() << endl;;

    for(int i=2;i<=n;i++){
        //頂点iは必要なので邪魔リストから省く
        bin.erase(i);
        for(auto x:path[i]){
            if(x < i)uf.unite(x,i);//iより小さい頂点はつなげる
            else bin.insert(x);//iより大きい頂点は邪魔リスト
        }

        //頂点１とすべて連結かの確認
        //集合のサイズと合わない場合連結していないことを指す。
        if(uf.siz[uf.root(1)] != i) cout << "-1" << endl;
        else cout << bin.size() << endl;
    }   
}

結果

ABCDE ５完　61:47 バーチャル参加

順位　1004位相当
パフォーマンス　1585相当

感想

今回は問題文を飲み込むのに時間がかかる問題が多かった印象。
しっかりと咀嚼する、向き合うことの大切さを再認識した。

最近は1000位代が続いているのでこのペースを維持していきたい