ABC410個人的備忘録［A-E］

自信を置き去りにした男の備忘録です

### コンテスト概要
CodeQUEEN 2025 予選 (AtCoder Beginner Contest 410)

https://atcoder.jp/contests/abc410

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

## [A - G1](https://atcoder.jp/contests/abc410/tasks/abc410_a)
#### 考察
明日は宝塚記念らしいですね。3歳以上の競走馬が対象らしいです。

さて、問題を簡単にすると『$K \leq A_i$となる$A_i$はいくつありますか？』ということ。forループを使えばおしまい。

#### 提出
``` c++:A.cpp
#include <bits/stdc++.h>
using namespace std;

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

    vector<int>num (n);//上限の値を管理する配列
    for(int i=0;i<n;i++) cin >> num[i];
    int k;
    cin >> k;//基準値

    int ans = 0;//答えカウンター
    for(auto x:num){
        if(x >= k) ans++;//上限が基準値以下ならカウンターを増やす
    }

    cout << ans << endl;
}
```

## [B - Reverse Proxy](https://atcoder.jp/contests/abc410/tasks/abc410_b)
#### 考察
最も数の少ない箱をどう管理しようか？とも考えたが箱は高々100個しかない。
なら、最適化なんてのは二の次。毎回全部の箱を調べてしまえ。

分岐する二重ループでOK。

#### 提出
``` c++:B.cpp
#include <bits/stdc++.h>
using namespace std;

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

    vector<int>num (n,0);//最初すべての箱は空
    for(int i=0;i<q;i++){
        if(i != 0) cout << " ";
        int x;
        cin >> x;

        if(x != 0){
            cout << x;
            num[x-1]++; //箱が指定されてるならそこに入れる
        }else{
            int y = -1,z = 101;
            for(int j=0;j<n;j++){
                //手前から見て最小値が更新されたら暫定の値を更新。
                //こうすれば同数の箱があっても最小番号がメモされる。
                if(z > num[j]){
                    z = num[j];
                    y = j+1;
                }
            }

            cout << y;
            num[y-1]++;//メモした番号の箱にボールを追加
        }
    }

    cout << "\n";
}
```

## [C - Rotatable Array](https://atcoder.jp/contests/abc410/tasks/abc410_c)
#### 考察
配列があって更新したり出力するだけ。
ただ、ローテーションが起こるのが厄介。kは最大$10^9$なので、本当にk回ローテーションさせる暇はない。何とかしてやったふりをしたい。

先頭の数字が一番後ろに行くというのを配列の要素数Nだけやれば、元の先頭が戻ってくる。つまりちょうどN回動かすことは何もしないのと同じ。なので配列を進めるべき回数はkをＮで割った余りだけになる。

とはいえＮは最大$10^6$なので余りの回数といえど実際に移動させるとTLEとなる。なので「配列」をいじるのではなく「今先頭はどこなのか？」をいじる。例えば配列を3移動させるなら「今の先頭は前から3番目」というふうに配列は大移動させないようにすればＯＫ。

後は出力、変更の時も今の先頭を参照しながら行えばＡＣ

#### 提出
``` c++:C.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    vector<int>num (n);
    for(int i=0;i<n;i++) num[i] = i+1;

    int rt = 0;//今の先頭が配列の何番目かを管理
    for(int i=0;i<q;i++){
        int c;
        cin >> c;

        if(c == 1){
            int p,x;
            cin >> p >> x;
            p--;

            p = (p+rt)%n;//今の先頭からp進んだところが更新ポイント
            num[p] = x;
        }
        if(c == 2){
            int p;
            cin >> p;
            p--;

            p = (p+rt)%n;//今の先頭からp進んだところが出力ポイント

            cout << num[p] << endl;
        }
        if(c == 3){
            int k;
            cin >> k;
            rt += k;
            rt %= n;//今まで進めた回数をnで割った余りが新たな先頭
        }
    }
    
}
```

## [D - XOR Shortest Walk](https://atcoder.jp/contests/abc410/tasks/abc410_D)
#### 考察
XOR。なんか、2週間に一回ぐらいいる気がする。
さて、XORの最小値を知りたいので十中八九全探査が要求される。

頂点数は$10^3$,辺の重みも$2^{10}=1024$。ということは全頂点のXORを管理してもかなり余裕がある。

ということで全頂点に対して「重みのXORの合計がＡになったことがあるか？」を管理するvectorを用意。あとはBFSとかで回し続ける。

答えは頂点Ｎの重みをすべて確認すればいい。

#### 提出
``` c++:D.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    vector<vector<pair<int,int>>>path (n,vector<pair<int,int>>(0));
    //頂点ごとにそこから向かう頂点と辺の重さを管理
    for(int i=0;i<m;i++){
        int a,b,w;
        cin >> a >> b >> w;
        a--,b--;

        path[a].push_back({b,w});
    }

    int lim = (1<<10);
    vector<vector<bool>>gone (n,vector<bool>(lim,false));
    //これまでにgone[頂点iが][jになったことがある]の真偽を管理
    gone[0][0] = true;//最初頂点１は重み０

    queue<pair<int,int>>que;
    que.push({0,0});

    while(!que.empty()){
        auto[x,w] = que.front();
        que.pop();

        for(auto [y,z]:path[x]){
            int p = (z^w);//今いるところから隣に行ったときの重みのXORを出す
            if(gone[y][p]) continue;//すでにpになったことがあるなら無視

            gone[y][p] = true;
            que.push({y,p});//次は頂点ｙで重みpの時を確認
        }
    }


    int ans = -1;//そもそもＮに行けないかもしれないのでー１にセット
    for(int i=0;i<lim;i++){
        if(gone[n-1][i]){
            //小さい順に見て頂点Ｎがiになったことがあるならそれが答え
            ans = i;
            break;
        }
    }

    cout << ans << endl;
}
```

## [E - Battles in a Row](https://atcoder.jp/contests/abc410/tasks/abc410_E)
#### 考察
全体的にDPの雰囲気を感じるので、DPでうまくやる方法を考える。
一番安直な方法としては
DP[i番目の敵までに][体力がjで][魔力がkのとき] = (倒した敵の数の最大)
が思いつく。ただこれはO(NHM)なので到底間に合わない。

そもそも、i-1番目の敵を倒せない限りi番目の敵までいけない。裏を返せばi番目の敵と対峙しているなら、倒した敵の数はi-1体に決まってる。なのでそもそもキーに倒した敵の数を入れるのは無駄。ここを改善したい。

ここで、魔力の最大値をキーにしてみる。すなわち、
DP[i番目の敵までに][体力がjのとき]　= （残り魔力の最大値)
とする。これならO(NH)なので問題なさそう。

順番に見ていき更新ができなかったとき。これはi番目の敵を倒せなかったということなので答えはi-1。全部倒せたならもちろん答えはＮ。

#### 提出
``` c++:E.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    vector<vector<int>>dp (n+1,vector<int>(h+1,-1));
    //dp[i番目の敵][体力がj]の時の魔力の最大値を管理
    //魔力が0でも体力があればなんとかなるので-1で初期化
    dp[0][h] = m;//もちろん最初は魔力もMAX

    for(int i=0;i<n;i++){
        int a,b;
        cin >> a >> b;
        
        bool c = true;
        for(int j=0;j<h+1;j++){
            if(dp[i][j] == -1) continue;//そんな状況がないならスキップ

            if(j >= a) dp[i+1][j-a] = max(dp[i+1][j-a],dp[i][j]), c = false;
            //体力に余裕があるなら物理攻撃
            if(dp[i][j] >= b) dp[i+1][j] = max(dp[i+1][j],dp[i][j] - b),c = false;
            //魔力に余裕があるなら魔法攻撃
        }

        if(c){//どんな体力でも攻撃できならたらそこまで。
            cout << i << endl;
            return 0;
        }
    }

    cout << n << endl;//全滅出来たらＮを出力
}
```

## 結果
ABCDE 5完　33:56

順位 906位
パフォーマンス　1614
レート　1313(+39)

## 感想
余りにも爆速で解けすぎてむしろ他もやすやすと抜けてるのではないかと不安だった。
Ｆ問題が解けず冷えてしまったのではないかと不安だった。

結果Ｆ問題はデカい崖、そしてシンプルに早かったので大勝。
でも早解き回はこけたら終わりなのでできるだけでないでくれ。