【ABC410 B問題】考察から実装(c++)まで

Last updated at 2025-06-17Posted at 2025-06-17

AtCoderBeginnerContest410の解説＆感想です。
コンテストリンク

問題一覧

B問題 - Reverse Proxy

問題リンク

問題概要

$1,2,...,N$と番号が付いた$N$個の箱がある。初め、全ての箱には$0$が書かれている。
$Q$個のクエリ$X_1,X_2,...,X_Q$を順番に処理する。

$X_i \gt 0$の時：箱$X_i$を1増やす
$X_i = 0$の時：一番小さい数字が書かれている箱の中で、一番番号が小さい箱の数字を$1$増やす

各クエリについて、増えた箱の番号を表示せよ。

制約

$1 \le N \le 100$
$1 \le Q \le 100$
$0 \le X_i \le N$

考察

簡単そうなクエリから処理したくなるのが人情。
とりあえず一つ目は数字を増やすだけなのでbox[x]++とかすれば良さそう。
二つ目も「一番小さい数字の中でいちばん左の場所を見つける」ができればいい。これはforとか書いてもいいけど、min_elementが使えそう。
計算量は一つ目のクエリが$O(1)$、二つ目のクエリは$O(N)$。クエリの個数が$Q$個なので、全体で$O(QN)$。

実装

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

int main(){
    //入力
    ll N,Q;
    cin>>N>>Q;
    
    //N個の箱を用意
    vll box(N, 0);
    
    //Q回クエリが入力される
    for(int i=0;i<Q;i++){
        ll X;
        cin>>X;
        
        if(X == 0){
            //クエリ1の処理
            ll minIdx = min_element(box.begin(), box.end()) - box.begin();
            box[minIdx]++;
            cout<<minIdx+1<<endl;
        }
        else{
            //クエリ2の処理
            box[X-1]++;
            cout<<X<<endl;
        }
    }
}

他の問題

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up