Zenn
🔵

【ABC369】AtCoder Beginner Contest 369【C++】

2024/09/01に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

AtCoder Beginner Contest 369

コンテストURL

https://atcoder.jp/contests/abc369

開催日

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

A: 369

解法

  • x がとりうる位置は最大 3 通り
  • 場合分けする
    • A = B のときは 1 通り
    • A と B の差が奇数であるときは 2 通り
    • A と B が異なり、差が偶数であるときは 3 通り
ABC369A.cpp
#include <iostream>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;

    if(a==b){
        cout << 1 << endl;
    }else if((a-b)%2!=0){
        cout << 2 << endl;
    }else{
        cout << 3 << endl;
    }

    return 0;
}

B: Piano 3

解法

  • 左手と右手を別々にシミュレーションする
  • 両手の最初の位置は、それぞれの最初に押す鍵盤の位置が最適である
ABC369B.cpp
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

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

    vector<int> L, R;
    int a;
    char s;
    for(int i=0; i<n; i++){
        cin >> a >> s;
        if(s=='L'){
            L.push_back(a);
        }else{
            R.push_back(a);
        }
    }

    int sum = 0;
    for(int i=1; i<L.size(); i++){
        sum += abs(L[i]-L[i-1]);
    }
    for(int i=1; i<R.size(); i++){
        sum += abs(R[i]-R[i-1]);
    }

    cout << sum << endl;
    return 0;
}

C: Count Arithmetic Subarrays

解法

  • 等差が続く回数を数えて、当該範囲に含まれる等差数列の組の数を計算することを繰り返す
  • 長さ 1 の数列と長さ 2 の数列は常に等差数列になるため、別途加算する
ABC369C.cpp
#include <iostream>
#include <vector>
using namespace std;

long long int calc(int x){
    long long int sum = 0;
    int cnt = 1;
    for(long long int i=x; i>=3; i--){
        sum += cnt;
        cnt++;
    }

    return sum;
}

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

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

    int cnt = 0;
    long long int ans = n + (n - 1);
    for(int i=1; i<n-1; i++){
        if((A[i+1]-A[i])==(A[i]-A[i-1])){
            cnt++;
        }else{
            ans += calc(cnt+2);
            cnt = 0;
        }
    }
    ans += calc(cnt+2);

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

D: Bonus EXP

解法

  • 動的計画法 (DP)
  • \text{dp}[i][j] := i 匹目まで出会い、モンスターを倒すのが偶数回目もしくは奇数回目 (j) であるときの経験値の合計の最大値
    • \text{dp}[i][0] = \max(\text{dp}[i-1][1]+2A_i, \text{dp}[i-1][0])
    • \text{dp}[i][1] = \max(\text{dp}[i-1][0]+A_i, \text{dp}[i-1][1])
  • \text{dp}[N][0] = 0, \text{dp}[N][1] = A_1 で初期化する
  • 答えは \max(\text{dp}[N][0], \text{dp}[N][1])
ABC369D.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

    vector<vector<long long int>> dp(n+1, vector<long long int>(2));
    dp[1][0] = 0;
    dp[1][1] = A[0];
    for(int i=1; i<n; i++){
        dp[i+1][0] = max(dp[i][1]+A[i]*2, dp[i][0]);
        dp[i+1][1] = max(dp[i][0]+A[i], dp[i][1]);
    }

    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

E: Sightseeing Tour

解法

  • ワーシャル・フロイド法 + 順列全探索 + bit 全探索
    • ワーシャル・フロイド法で全点対最短経路を求めておく
    • 順列全探索で与えられた橋を渡る順番を決める
    • bit 全探索で各橋を渡る向きを決める
ABC369E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

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

    const long long int INF = 1e18;
    vector<vector<long long int>> G(n, vector<long long int>(n, INF));
    int u, v;
    long long int t;
    vector<tuple<int, int, int>> B;
    for(int i=0; i<m; i++){
        cin >> u >> v >> t;
        u--;
        v--;
        G[u][v] = min(G[u][v], t);
        G[v][u] = min(G[v][u], t);
        B.emplace_back(u, v, t);
    }

    for(int i=0; i<n; i++){
        G[i][i] = 0;
    }
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
            }
        }
    }

    int q;
    cin >> q;
    for(int i=0; i<q; i++){
        int k;
        cin >> k;
        vector<int> K(k);
        for(int j=0; j<k; j++){
            cin >> K[j];
            K[j]--;
        }

        // sort(K.begin(), K.end());

        long long int minv = INF;
        do{
            for(int l=0; l<(1<<k); l++){
                int now = 0;
                long long int sum = 0;
                for(int m=0; m<k; m++){
                    if(l&(1<<m)){
                        auto [u, v, t] = B[K[m]];
                        sum += G[now][v];
                        sum += t;
                        now = u;
                    }else{
                        auto [u, v, t] = B[K[m]];
                        sum += G[now][u];
                        sum += t;
                        now = v;
                    }
                }
                sum += G[now][n-1];
                minv = min(minv, sum);
            }
        }while(next_permutation(K.begin(), K.end()));

        cout << minv << endl;
    }

    return 0;
}

F: Sightseeing Tour

解法

  • 最長増加部分列 (LIS) を求める
  • コインの位置を vector<pair<int, int>> に記録して昇順にソートする
  • (r_i, c_i) と (r_j, c_j) の両方を拾えるのは、 (r_i \leqq r_j) \land (c_i \leqq c_j) のとき
    • r_i \leqq r_j は vector<pair<int, int>> の昇順ソートで完了しているから、 c について最長広義増加部分列を求める問題に帰着される
  • 最長広義増加部分列を復元するためにインデックスを記録することに注意する
ABC369F.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int h, w, n;
    cin >> h >> w >> n;

    int r, c;
    vector<pair<int, int>> C;
    for(int i=0; i<n; i++){
        cin >> r >> c;
        r--;
        c--;
        C.emplace_back(r, c);
    }

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

    vector<int> V, id, pre(n, -1);
    for(int i=0; i<n; i++){
        auto [r, c] = C[i];
        auto it = upper_bound(V.begin(), V.end(), c);
        int idx = it - V.begin();

        if(it==V.end()){
            V.push_back(c);
            id.push_back(i);
        }else{
            V[idx] = c;
            id[idx] = i;
        }

        if(idx>0){
            pre[i] = id[idx-1];
        }
    }

    vector<pair<int, int>> ans;
    ans.emplace_back(h-1, w-1);
    int now = id.back();
    while(now!=-1){
        ans.emplace_back(C[now]);
        now = pre[now];
    }
    ans.emplace_back(0, 0);
    reverse(ans.begin(), ans.end());

    string s;
    for(int i=0; i<ans.size()-1; i++){
        int down = ans[i+1].first - ans[i].first;
        int right = ans[i+1].second - ans[i].second;
        while(down){
            s.push_back('D');
            down--;
        }
        while(right){
            s.push_back('R');
            right--;
        }
    }

    cout << V.size() << endl;
    cout << s << endl;
    return 0;
}

Discussion