AtCoder ABC410 振り返り #C++

はじめに

ABC410に参加したので振り返ります。
結果は1完でした。（コンテスト成績表）
今回はA, B問題についてまとめていきます。

A - G1

条件分岐でカウントしていくだけでした。

• diff：12
• 計算量：$O(N)$

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

int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int K;
    cin >> K;

    int counter = 0;

    for (int i = 0; i < N; i++) {
        if (K <= A[i]) {
            counter++;
        }
    }
    cout << counter << endl;
}

B - Reverse Proxy

本番の提出ではWAになりました。
原因はボールの数が最小の箱の探索とボールの追加を同時に行っていたことでした。あと配列の数え間違いですね。

• diff：57
• 計算量：$O(N * Q)$

// WAのコード
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, Q;
    cin >> N >> Q;
    int X[N];
    for (int i = 0; i < N; i++) {
        cin >> X[i];
    }

    int box[Q];
    int ans[N];
    for (int i = 0; i < Q; i++) {
        if (X[i] != 0) {
            box[i]++;
            ans[i] = X[i];
        } else {
            int min = 101;
            int address = 0;
            for (int j = N; j > 0; j--) {
                if (box[j] <= min) {
                    min = box[j];
                    address = j;
                }
                box[address]++;
                ans[i] = address;
            }
        }
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << ' ';
    } 
    cout << endl;
}

// ACのコード
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, Q, A[101];
    cin >> N >> Q;
    for (int i = 1; i <= Q; i++) {
        int x;
        cin >> x;
        if (x > 0) {
            A[x]++;
            cout << x << ' ';
        } else {
            int MQ = 101;
            for (int j = 1; j <= N; j++) {
                if (A[j] < MQ) {
                    MQ = A[j];
                }
            } for (int j = 1; j <= N; j++) {
                if (A[j] == MQ) {
                    A[j]++;
                    cout << j << ' ';
                    break;
                }
            }
        }
    }
}

おわりに

今回はアルゴリズムというよりも文章の読解力と実装力の不足が目立ちました。ABC411に向けて精進を頑張っていきたいです。