【ABC362】AtCoder Beginner Contest 362【C++】

コンテスト名

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

コンテストURL

開催日

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

---

A: Buy a Pen

解法

• 問題文通り $C$ の値によって場合分けして解く

ABC362A.cpp

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

int main(){
    int r, g, b;
    cin >> r >> g >> b;

    string c;
    cin >> c;

    if(c=="Red"){
        cout << min(g, b) << endl;
    }else if(c=="Green"){
        cout << min(r, b) << endl;
    }else if(c=="Blue"){
        cout << min(r, g) << endl;
    }

    return 0;
}

B: Right Triangle

解法

• ベクトルの内積を考える
  • 2 つのベクトルが直交するとき内積は 0 である
• $\overrightarrow{AB}, \overrightarrow{BC}, \overrightarrow{CA}$ のうち直交する組み合わせがあるか判定する
  • $\overrightarrow{AB} = (x_B - x_A, y_B - y_A)$
  • $\overrightarrow{BC} = (x_C - x_B, y_C - y_B)$
  • $\overrightarrow{CA} = (x_A - x_C, y_A - y_C)$
• 例えば、 $\overrightarrow{AB} \cdot \overrightarrow{BC} = (x_B - x_A) \times (x_C - x_B) + (y_B - y_A) \times (y_C - y_B) = 0$ のとき、辺 $AB$ と辺 $BC$ は直交する

ABC362B.cpp

#include <iostream>
using namespace std;

int main(){
    int xa, ya, xb, yb, xc, yc;
    cin >> xa >> ya >> xb >> yb >> xc >> yc;

    int abx = xb - xa, aby = yb - ya;
    int bcx = xc - xb, bcy = yc - yb;
    int cax = xa - xc, cay = ya - yc;

    if(abx*bcx+aby*bcy==0 || bcx*cax+bcy*cay==0 || cax*abx+cay*aby==0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

C: Sum = 0

解法

• すべての $i = 1, 2, \cdots, N$ について、 $X_i = L_i$ となる場合を考え、足りない分を補充する
  • $\sum\limits_{i=1}^{N} X_i= 0$ となるまで各 $X_i$ に補充する
  • 最大 $R_i - L_i$ の分だけ補充できる

ABC362C.cpp

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

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

    vector<long long int> L(n), R(n), D(n);
    long long int diffsum = 0, lsum = 0;
    for(int i=0; i<n; i++){
        cin >> L[i] >> R[i];
        lsum += L[i];
        D[i] = R[i] - L[i];
        diffsum += D[i];
    }

    if(lsum<=0 && diffsum>=abs(lsum)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
        return 0;
    }

    for(int i=0; i<n; i++){
        if(i){
            cout << " ";
        }

        if(lsum==0){
            cout << L[i];
        }else if(abs(lsum)>=D[i]){
            cout << L[i] + D[i];
            lsum += D[i];
        }else if(abs(lsum)<D[i]){
            cout << L[i] + abs(lsum);
            lsum += abs(lsum);
        }
    }

    cout << endl;
    return 0;
}

D: Shortest Path 3

解法

• ダイクストラ法
• 辺に重みがある通常のダイクストラ法において、頂点にも重みがある場合を考える
• 頂点 $i$ の重み $A_i$ は、頂点 $i$ に向かうことが決定したときに加算する
  • 辺 $j$ を通って頂点 $X$ から頂点 $Y$ に移動するときの頂点 $Y$ までの総コストは、頂点 $X$ までのコスト $+ B_j + A_{Y}$ であるとみなす

ABC362D.cpp

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

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

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

    vector<vector<pair<int, int>>> G(n);
    int u, v, b;
    for(int i=0; i<m; i++){
        cin >> u >> v >> b;
        u--;
        v--;
        G[u].emplace_back(v, b);
        G[v].emplace_back(u, b);
    }

    const long long int INF = 1e18;
    vector<long long int> dist(n, INF);
    priority_queue<pair<long long int, int>, vector<pair<long long int, int>>, greater<pair<long long int, int>>> Q;
    dist[0] = A[0];
    Q.emplace(A[0], 0);
    while(!Q.empty()){
        auto [d, now] = Q.top();
        Q.pop();

        if(dist[now]!=d){
            continue;
        }

        for(int i=0; i<G[now].size(); i++){
            auto [next, cost] = G[now][i];
            if(d+cost+A[next]>=dist[next]){
                continue;
            }
            dist[next] = d + cost + A[next];
            Q.emplace(d+cost+A[next], next);
        }
    }

    for(int i=1; i<n; i++){
        if(i-1){
            cout << " ";
        }
        cout << dist[i];
    }

    cout << endl;
    return 0;
}

E: Count Arithmetic Subsequences

解法

• 動的計画法 (DP)
• $\text{dp} [i][k][d]$ := 初項が $A_i$ 、長さが $k$ 、公差が $d$ である等差数列の場合の数
  • 公差 $d$ は $-(10^9 - 1)$ から $10^9 - 1$ までとりうるため、map<int, long long int> で管理する
  • 動的計画法全体は vector<vector<map<int, long long int>>> で管理する
• 長さ $1$ と長さ $2$ の等差数列は別途計算することに注意する

ABC362E.cpp

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

int main(){
    const int MOD = 998244353;
    int n;
    cin >> n;

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

    vector<vector<map<int, long long int>>> dp(n+1, vector<map<int, long long int>>(n+1));
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            int d = A[i] - A[j];
            for(int k=0; k<=i; k++){
                dp[i][k+1][d] += dp[j][k][d]%MOD;
                dp[i][k+1][d] %= MOD;
            }
            dp[i][2][d] += 1;
            dp[i][2][d] %= MOD;
        }
    }

    cout << n;
    for(int i=2; i<=n; i++){
        long long int sum = 0;
        for(int j=0; j<n; j++){
            for(auto [d, cnt] : dp[j][i]){
                sum += cnt%MOD;
                sum %= MOD;
                
            }
        }
        cout << " " << sum;
    }

    cout << endl;
    return 0;
}