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

石橋を叩いただけの男の備忘録です

コンテスト概要

日本レジストリサービス（JPRS）プログラミングコンテスト2025#2（AtCoder Beginner Contest 415）

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

A - Unsupported Type

考察

シンプルすぎていうことがない。
forループを回して検索するだけ。

ただ、少し変なことがしたくなる。
制約が100なので、配列に答えを入れていく方針で実装。

まぁ奇をてらうとバグになりやすいのでできればやめましょう。

提出

A.cpp

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

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

    vector<string>num (101,"No");/どんな値でも答えられるようにする。
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        num[x] = "Yes";//１つでもあったらYes。
    }

    int x;
    cin >> x;
    cout << num[x] << endl; //確認したい奴だけを出力。
}

B - Pick Two

考察

手前から見て２つずつ出力するだけ。
むしろ出力方法のほうが不安。

今回は見つけた順に位置を出力。
その後、箱が奇数個目なら","、偶数個目なら改行すればいい。
問題文の設定が凝ってるわりには簡単だった。

提出

B.cpp

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

int main(){
    string s;
    cin >> s;

    int len = s.length();//文字列の長さを取得
    int now = 0;//今が偶数個目か、奇数個目かを確認する変数。
    for(int i=0;i<len;i++){
        if(s[i] != '#') continue;　//箱じゃないなら無視
        cout << i+1;　//とりあえず場所を出力

        if(now == 0) cout << ',';　//奇数ならコンマ
        else cout << endl;//偶数なら改行

        now = (now+1)%2;　//変数も変えておく
    }    
}

C - Mixture

考察

前回に続き今回のC問題も厄介そうという印象。
やってみればそうでもなかった。

薬品は高々18個。となると、遷移のパターンは$2^{18} = 262144$通りしかない。
じゃあ、とりあえず適当な順番で混ぜていけばいい。
状態Nの時、まだ入れてない薬品を順番に入れていく。実装としてはBFSとかで何とかなる。

最終的に全部交ざる、すなわち状態$2^N-1$になれればYes。無理ならNo。

350点問題振れ幅がデカすぎる。

提出

A.cpp

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

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

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

        int lim = (1<<n);//状態は全部で2^nパターン
        vector<bool>gone (lim,false);//どの状態になったことがあるかを管理
        queue<int>que;
        que.push(0);
        gone[0] = true;//空っぽは当然安全

        while(!que.empty()){
            int now = que.front();
            que.pop();
            if(now == lim-1) break;//混ぜ切ってるなら無視
            
            for(int i=0;i<n;i++){
                if(now&(1<<i)) continue;//すでに入れたことのある薬品は飛ばす
                int nex = now + (1<<i);//とりあえず混ぜる
                if(gone[nex]) continue;//すでに起こった状態なら飛ばす
                if(s[nex-1] == '1') continue;//危険なら飛ばす

                gone[nex] = true;　//状態にマークを付ける
                que.push(nex);
            }
        }

        //最後まで行けたかチェック
        if(gone[lim-1]) cout << "Yes" << endl;　
        else cout << "No" << endl;
    }
    
}

D - Get Many Stickers

考察

「なんか多湖輝の『頭の体操』ぽい問題だなぁ」とか思ってた。
できるだけシールが欲しいので、交換する際にコーラの本数をできるだけ減らしたくない。

なので、コスパのいいコーラからどんどん交換していきたい。
ではその「コスパ」はどうやって図るか？
例えばA本でB本と交換できるなら、損失はA-B本。この「A-B」が小さいい順にやっていけばよさそう。

あとは、手元のコーラがA本未満の時は交換できないことに気を付けながらガンガン交換。

こういったプログラミングのごり押し好き。

提出

D.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>>;

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

    p_que<pair<ll,ll>>que;
    for(int i=0;i<m;i++){
        ll a,b;
        cin >> a >> b;

        que.push({a-b,a});//それぞれ｛減る量、最低必要な本数｝で管理
    }

    ll ans = 0;
    while(!que.empty() && n != 0){
        auto[res,lim] = que.top();//減る量が少ない順に交換
        que.pop();
        if(n < lim) continue;//手元のコーラが最低数未満なら飛ばす
        ll dis = n - lim ;//最低数と手持ちの差を出す。
        ll cnt = (dis / res) + 1LL;
        //差がなくなるまで交換。
        //そうすると手持ちは最低数ギリギリなのであと1つ交換できる。
        ans += cnt;//シールをもらう。
        n -= cnt*res;//コーラを減らす。
    }

    cout << ans << endl;
}

E - Hungry Takahashi

考察

どうせTLEしそうと思って飛ばしたらそうでもなかった。
とりあえず高橋君に適当なお金を持たせておく。

全てのマスに対して、お金を貰う→食べ物を買うを繰り返す。
もし、借金したらそのマスは失敗。
最終的に最後のマスまで借金をしなかったかを確認する。
一度も借金していないならOK、そうでないならNG。
これの確認にはO(HW)かかる。

じゃあ適当なお金はどう決めるかだが、まあ二分探査でどうにでもなる。
制約的に$2\times 10^{14}$円持ってれば間違いないのでこの範囲を調べればOK。

制限時間も3秒だったんですね。確認すればよかった。

提出

E.cpp

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

int main(){
    ll h,w;
    cin >> h >> w;
    vector<vector<ll>>coin (h,vector<ll>(w));//落ちてるお金を管理
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++) cin >> coin[i][j];
    }

    ll days = h+w-1;
    vector<ll>pri (days);
    for(int i=0;i<days;i++) cin >> pri[i];//N日目の金額を管理

    ll a = 0LL,b = 2e14 + 1LL;　//最大2×10^14円あればいい。
    while(a != b){
        ll bgn = (a+b)/2LL; //仮の金額
        vector<vector<ll>>mny (h,vector<ll>(w,-1LL));
        //そのマスで1度も借金を負わずに持てる最大の金額
        mny[0][0] = bgn;
        //最初のお金を持っておく

        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                //上と左のマスのうちより多くのお金を持ってるほうを現在の所持金に
                if(i != 0) mny[i][j] = max(mny[i][j],mny[i-1][j]);
                if(j != 0) mny[i][j] = max(mny[i][j],mny[i][j-1]);
                if(mny[i][j] < 0) continue;
                //どうあがいても借金なら飛ばす。

                mny[i][j] += coin[i][j];
                mny[i][j] -= pri[i+j];
                //本日分の清算
            }
        }

        

        if(mny[h-1][w-1] >= 0) b = bgn;　//借金していないなら最初のお金で十分
        else a = bgn + 1LL;//借金したならもっと必要
    }

    cout << a << endl;

}

F - Max Combo

考察

先にこっちをやったがどうもならなかった。
要するに「すごいセグメントツリー」を作ればいいことは分かってたんですが。実装がどうしようにもありませんでした。

結果

ABCDE 5完　96:34

順位 1697位
パフォーマンス　1284
レート 1346(-7)

感想

まぁ、完全なる選択ミスですね。
ちゃんとE問題と向き合えばよかった。

というか、ここ最近解けてないE問題ないんだからちゃんとやればいいのに。

順位表見る癖を付けます。