【ABC374】AtCoder Beginner Contest 374【C++】

コンテスト名

キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）

コンテストURL

開催日

2024/10/05 21:00-22:40

---

A: Takahashi san 2

解法

• 問題文通りに判定する

ABC374A.cpp

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

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

    if(s.substr(s.size()-3)=="san"){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B: Unvarnished Report

解法

• 文字列の長さが異なる場合に注意して問題文通りに判定する

ABC374B.cpp

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

int main(){
    string s, t;
    cin >> s >> t;

    int n = min(s.size(), t.size());
    for(int i=0; i<n; i++){
        if(s[i]!=t[i]){
            cout << i+1 << endl;
            return 0;
        }
    }

    if(s.size()!=t.size()){
        cout << n+1 << endl;
    }else{
        cout << 0 << endl;
    }

    return 0;
}

C: Separated Lunch

解法

1. bit 全探索
2. 再帰関数

• それぞれの部署をどちらのグループに割り当てるか全探索する

ABC374C_1.cpp

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

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

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

    int minv = 3e9;
    for(int i=0; i<(1<<n); i++){
        int a = 0, b = 0;
        for(int j=0; j<n; j++){
            if(i&(1<<j)){
                a += K[j];
            }else{
                b += K[j];
            }
        }
        minv = min(minv, max(a, b));
    }

    cout << minv << endl;

    return 0;
}

ABC374C_2.cpp

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

int n;
vector<int> K;
int minv = 3e9;
int a = 0, b = 0;

void dfs(int num){
    if(num==n){
        minv = min(minv, max(a, b));
        return;
    }

    a += K[num];
    dfs(num+1);
    a -= K[num];

    b += K[num];
    dfs(num+1);
    b -= K[num];

    return;
}

int main(){
    cin >> n;

    K.resize(n);
    for(int i=0; i<n; i++){
        cin >> K[i];
    }

    dfs(0);

    cout << minv << endl;

    return 0;
}

D: Laser Marking

解法

• 順列全探索 + bit 全探索
• 順列全探索で線分の順番を探索する
• bit 全探索で各線分の移動方向を探索する

ABC374D.cpp

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

int main(){
    int n, s, t;
    cin >> n >> s >> t;

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

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

    double minv = 1e9;
    do{
        for(int i=0; i<(1<<n); i++){
            double sum = 0;
            for(int j=0; j<n; j++){
                if(i&(1<<j)){
                    sum += sqrt(pow(A[V[j]]-C[V[j]], 2) + pow(B[V[j]]-D[V[j]], 2))/t;
                    if(j){
                        if(i&(1<<(j-1))){
                            sum += sqrt(pow(A[V[j]]-C[V[j-1]], 2) + pow(B[V[j]]-D[V[j-1]], 2))/s;
                        }else{
                            sum += sqrt(pow(A[V[j]]-A[V[j-1]], 2) + pow(B[V[j]]-B[V[j-1]], 2))/s;
                        }
                    }else{
                        sum += sqrt(pow(A[V[j]], 2) + pow(B[V[j]], 2))/s;
                    }
                }else{
                    sum += sqrt(pow(A[V[j]]-C[V[j]], 2) + pow(B[V[j]]-D[V[j]], 2))/t;
                    if(j){
                        if(i&(1<<(j-1))){
                            sum += sqrt(pow(C[V[j]]-C[V[j-1]], 2) + pow(D[V[j]]-D[V[j-1]], 2))/s;
                        }else{
                            sum += sqrt(pow(C[V[j]]-A[V[j-1]], 2) + pow(D[V[j]]-B[V[j-1]], 2))/s;
                        }
                    }else{
                        sum += sqrt(pow(C[V[j]], 2) + pow(D[V[j]], 2))/s;
                    }
                }
            }
            minv = min(minv, sum);
        }
    }while(next_permutation(V.begin(), V.end()));

    printf("%.9lf\n", minv);

    return 0;
}

E: Sensor Optimization Dilemma 2

解法

• 答えを二分探索する
• 機械 $S_i$ と $T_i$ の導入数の求め方に注意する
  • 機械 $S_i$ のほうがコスパが悪いとき、 機械 $S_i$ の導入台数は必ず $B_i$ 台未満となる
    • $B_i$ 台 の機械 $S_i$ による製造能力 ($A_i \times B_i$) は、 $A_i$ 台の機械 $T_i$ による製造能力 ($B_i \times A_i$) で代替できるから
  • 機械 $T_i$ のほうがコスパが悪いとき、 機械 $T_i$ の導入台数は必ず $A_i$ 台未満となる
    • $A_i$ 台 の機械 $T_i$ による製造能力 ($B_i \times A_i$) は、 $B_i$ 台の機械 $S_i$ による製造能力 ($A_i \times B_i$) で代替できるから
• $\lceil \frac{x}{y} \rceil = \lfloor \frac{x + y - 1}{y} \rfloor$

ABC374E.cpp

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

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

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

    long long int low = -1, high = x*100+1;
    while(high-low>1){
        long long int mid = low + (high-low)/2;
        bool flag = true;

        long long int sum = 0;
        for(int i=0; i<n; i++){
            long long int a = 1e9, b = 1e9;

            for(int j=0; j<A[i]; j++){
                a = min(a, (long long int)j*Q[i] + ((max(0LL, mid-B[i]*j) + A[i] - 1)/A[i])*P[i]);
            }
            for(int j=0; j<B[i]; j++){
                b = min(b, (long long int)j*P[i] + ((max(0LL, mid-A[i]*j) + B[i] - 1)/B[i])*Q[i]);
            }

            sum += min(a, b);

            if(sum>x){
                flag = false;
                break;
            }
        }
        
        if(flag){
            low = mid;
        }else{
            high = mid;
        }
    }

    cout << low << endl;

    return 0;
}