【ABC401】AtCoder Beginner Contest 401【C++】

コンテスト名

AtCoder Beginner Contest 401

コンテストURL

開催日

2025/04/12 21:00–22:40

---

A: Status Code

解法

• 問題文通りに判定する

ABC401A.cpp

#include <iostream>
using namespace std;

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

    if(s>=200 && s<=299){
        cout << "Success" << endl;
    }else{
        cout << "Failure" << endl;
    }

    return 0;
}

B: Unauthorized

解法

• ログイン状態について記録しておき、問題文通りに操作する

ABC401B.cpp

#include <iostream>
#include <string>
using namespace std;

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

    bool flag = false;
    string s;
    int cnt = 0;
    for(int i=0; i<n; i++){
        cin >> s;
        if(s=="login"){
            flag = true;
        }else if(s=="logout"){
            flag = false;
        }else if(s=="public"){
            continue;
        }else if(s=="private"){
            if(!flag){
                cnt++;
            }
        }
    }

    cout << cnt << endl;

    return 0;
}

C: K-bonacci

解法

• 差分を利用する
• $K \leqq N$ のとき
  • $i < K$ のとき、 $A_i = 1$
  • $A_K = K$
  • $i > K$ のとき、 $A_i = A_{i-1} + A_{i-1} - A_{i-K-i}$
• $K > N$ のとき、 $A_N = 1$ であることに注意する

ABC401C.cpp

#include <iostream>
#include <vector>
using namespace std;

long long int mod(long long int x, long long int m){
    long long int res = x % m;
  
    if(res<0){
      res += m;
    }
  
    return res;
}

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

    if(k>n){
        cout << 1 << endl;
        return 0;
    }

    vector<long long int> A(n+1);
    for(int i=0; i<k; i++){
        A[i] = 1;
    }

    int j = 0;
    A[k] = k;
    for(int i=k+1; i<=n; i++){
        A[i] = 2 * A[i-1] - A[j];
        j++;
        A[i] = mod(A[i], 1000000000);
    }

    cout << mod(A[n], 1000000000) << endl;

    return 0;
}