【ABC364】AtCoder Beginner Contest 364【C++】

コンテスト名

日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

コンテストURL

https://atcoder.jp/contests/abc364

開催日

2024/07/27 21:00-22:40

---

A: Glutton Takahashi

解法

• 2 つ連続で甘い料理が続くかを判定する
• 最後の料理の判定に注意する

ABC364A.cpp

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

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

    string s, t = "salty";
    bool flag = true;
    for(int i=0; i<n; i++){
        cin >> s;
        if(s=="sweet" && s==t && i<n-1){
            flag = false;
        }
        t = s;
    }

    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B: Grid Walk

解法

• 問題文通りにシミュレーションする

ABC364B.cpp

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

int main(){
    int h, w, x, y;
    cin >> h >> w >> x >> y;
    x--;
    y--;

    vector<vector<char>> G(h, vector<char>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> G[i][j];
        }
    }

    string X;
    cin >> X;

    for(int i=0; i<X.size(); i++){
        if(X[i]=='L' && y>0 && G[x][y-1]=='.'){
            y--;
        }else if(X[i]=='R' && y<w-1 && G[x][y+1]=='.'){
            y++;
        }else if(X[i]=='U' && x>0 && G[x-1][y]=='.'){
            x--;
        }else if(X[i]=='D' && x<h-1 && G[x+1][y]=='.'){
            x++;
        }
    }

    cout << x+1 << " " << y+1 << endl;
    return 0;
}

C: Minimum Glutton

解法

• 甘さの降順にソートした配列としょっぱさの降順にソートした配列を用意して、それぞれ順番に判定し、少ないほうが求める答えである
• すべての料理を食べることができる場合に注意する

ABC364C.cpp

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

int main(){
    int n;
    cin >> n;
    long long int x, y;
    cin >> x >> y;

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

    sort(A.rbegin(), A.rend());
    sort(B.rbegin(), B.rend());

    for(int i=0; i<n; i++){
        x -= A[i];
        y -= B[i];
        if(x<0 || y<0){
            cout << i+1 << endl;
            return 0;
        }
    }

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

D: K-th Nearest

解法

• 答えを二分探索で求める
• 条件を満たす点 $X$ と点 $B_j$ の距離を二分探索で求める

ABC364D.cpp

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

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

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

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

    int b, k;
    for(int i=0; i<q; i++){
        cin >> b >> k;

        int left = 0, right = 1e9;
        while(right-left>1){
            int mid = left + (right - left)/2;
            int r = lower_bound(A.begin(), A.end(), b+mid) - A.begin();
            int l = upper_bound(A.begin(), A.end(), b-mid) - A.begin();
            if(r-l>=k){
                right = mid;
            }else{
                left = mid;
            }
        }

        cout << left << endl;
    }

    return 0;
}

E: Maximum Glutton

解法

• 動的計画法 (DP)
• $\text{dp}[i][j][k]$ := $i$ 個目の料理まで決定し、甘さの合計が $j$ で、料理を $k$ 個食べるときのしょっぱさの合計の最小値

ABC364E.cpp

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

int main(){
    int n, x, y;
    cin >> n >> x >> y;

    vector<int> A(n), B(n);
    for(int i=0; i<n; i++){
        cin >> A[i] >> B[i];
    }
    
    const int INF = 1e9;
    vector<vector<int>> dp(x+1, vector<int>(n+1, INF));
    dp[0][0] = 0;
    for(int i=0; i<n; i++){
        vector<vector<int>> old(x+1, vector<int>(n+1, INF));
        swap(dp, old);

        for(int j=0; j<=x; j++){
            for(int k=0; k<=n; k++){
                int now = old[j][k];
                if(now==INF){
                    continue;
                }
                dp[j][k] = min(dp[j][k], old[j][k]);

                if(j+A[i]<=x){
                    dp[j+A[i]][k+1] = min(dp[j+A[i]][k+1], now+B[i]);
                }
            }
        }
    }

    int ans = 0;
    for(int j=0; j<=x; j++){
        for(int k=0; k<=n; k++){
            if(dp[j][k]<=y){
                ans = max(ans, k);
            }
        }
    }

    if(ans<n){
        ans++;
    }

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