【ABC365】AtCoder Beginner Contest 365【C++】

コンテスト名

トヨタ自動車プログラミングコンテスト2024#8（AtCoder Beginner Contest 365）

コンテストURL

開催日

2024/08/03 21:00-22:40

---

A: Leap Year

解法

• 問題文通りに判定する

ABC365A.cpp

#include <iostream>
using namespace std;

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

    if(y%4!=0){
        cout << 365 << endl;
    }else if(y%100!=0){
        cout << 366 << endl;
    }else if(y%400!=0){
        cout << 365 << endl;
    }else{
        cout << 366 << endl;
    }

    return 0;
}

B: Second Best

解法

• vector<pair<int, int>> で要素の値と位置を記録する
• 降順にソートして 2 番目に大きい要素を取得する

ABC365B.cpp

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

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

    vector<pair<int, int>> A;
    int a;
    for(int i=0; i<n; i++){
        cin >> a;
        A.emplace_back(a, i+1);
    }

    sort(A.rbegin(), A.rend());
    auto [value, num] = A[1];
    cout << num << endl;
    return 0;
}

C: Transportation Expenses

解法

1. 累積和を利用して仮の上限額を求める
   • 交通費の配列 $A$ を昇順にソートして累積和を求める
   • 仮の上限額 $x'$ を $A_i$ のなかから選ぶ
   • 交通費が仮の上限額 $x'$ 以下の人 $i$ には $A_i$ 円が支給されるため、累積和を利用して合計を求める
   • 交通費が仮の上限額 $x'$ より大きい人には $x'$ 円が支給されるため、（交通費が仮の上限額 $x'$ より大きい人の人数 $\times \ x'$ ）を求める
   • $M$ 円からこれらの総和を引いた残りの分を交通費が仮の上限額 $x'$ より大きい人に分配する
   • $A$ の最大値を $x$ にしたときでも交通費補助額の総和が $M$ 円以下になるならば、答えは無限になる
   • $A$ の最小値を仮の上限額 $x'$ にしたときでも条件を満たせない場合は、 $\lfloor \frac{M}{N} \rfloor$ が答えである
   • 計算量は $O(N \log N)$
2. 答えを二分探索で求める
   • 交通費の配列 $A$ を昇順にソートして答えを二分探索で求める
   • 計算量は $O(N \log (\text{max}A))$

ABC365C_1.cpp

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

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

    vector<long long int> A(n), S(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
        S[i] = A[i];
    }

    sort(A.begin(), A.end());
    sort(S.begin(), S.end());

    for(int i=1; i<n; i++){
        S[i] += S[i-1];
    }

    for(int i=n-1; i>=0; i--){
        long long int sum = S[i];
        sum += A[i] * (n - 1 - i);

        if(sum<=m){
            if(A[i]==A[n-1]){
                cout << "infinite" << endl;
            }else{
                cout << A[i] + (m - sum)/(n - 1 - i) << endl;
            }
            return 0;
        }
    }

    cout << m / n << endl;
    return 0;
}

ABC365C_2.cpp

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

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

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

    sort(A.begin(), A.end());

    int low = 0, high = A.back() + 1;
    while(high-low>1){
        int mid = low + (high - low)/2;

        long long int sum = 0;
        for(int i=0; i<n; i++){
            sum += min(mid, A[i]);
        }

        if(sum<=m){
            low = mid;
        }else{
            high = mid;
        }
    }

    if(low>=A.back()){
        cout << "infinite" << endl;
    }else{
        cout << low << endl;
    }

    return 0;
}

D: AtCoder Janken 3

解法

• 動的計画法 (DP)
• $\text{dp}[i][j]$ := $i$ 回目に手 $j$ を出すときの勝った回数の最大値
• $\text{R} = 0, \text{P} = 1, \text{S} = 2$ とすると、 $i - 1$ 回目の結果から求められる
  • 相手が $i$ 回目に $\text{R} = 0$ を出したとき
    • あいこ： $\text{dp}[i][0] = \text{max}(\text{dp}[i-1][1], \text{dp}[i-1][2])$
    • 勝ち： $\text{dp}[i][1] = \text{max}(\text{dp}[i-1][0], \text{dp}[i-1][2]) + 1$

ABC365D.cpp

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

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

    string s;
    cin >> s;

    vector<vector<int>> dp(n+1, vector<int>(3));
    for(int i=0; i<n; i++){
        if(s[i]=='R'){
            dp[i+1][0] = max(dp[i][1], dp[i][2]);
            dp[i+1][1] = max(dp[i][0], dp[i][2]) + 1;
        }else if(s[i]=='P'){
            dp[i+1][1] = max(dp[i][0], dp[i][2]);
            dp[i+1][2] = max(dp[i][0], dp[i][1]) + 1;
        }else if(s[i]=='S'){
            dp[i+1][2] = max(dp[i][0], dp[i][1]);
            dp[i+1][0] = max(dp[i][1], dp[i][2]) + 1;
        }
    }

    int ans = 0;
    for(int i=0; i<3; i++){
        ans = max(ans, dp[n][i]);
    }

    cout << ans << endl;
    return 0;
}