【ABC359】AtCoder Beginner Contest 359【C++】

コンテスト名

ユニークビジョンプログラミングコンテスト2024 夏（AtCoder Beginner Contest 359）

コンテストURL

開催日

2024/06/22 21:00-22:40

---

A: Count Takahashi

解法

• 文字列が等しいか判定する

ABC359A.cpp

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

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

    string s;
    int cnt = 0;
    for(int i=0; i<n; i++){
        cin >> s;
        if(s=="Takahashi"){
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}

B: Couples

解法

• $A_i = A_{i+2}$ を満たす $i$ の個数を求める

ABC359B.cpp

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

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

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

    int cnt = 0;
    for(int i=0; i<2*n-2; i++){
        if(A[i]==A[i+2]){
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}

C: Tile Distance 2

解法

• 処理を簡単にするためにスタートとゴールの座標はタイルの一方の端に揃える
• $y$ 軸方向に移動すると、移動できる $x$ 軸方向の範囲が増えることに注意する
  • $x$ 軸方向の移動と $y$ 軸方向の移動の大小によって計算が異なる

ABC359C.cpp

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

int main(){
    long long int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    if((sx+sy)%2==0){
        sx++;
    }
    if((tx+ty)%2==0){
        tx++;
    }

    long long int ans = 0;
    if(abs(sx-tx)<=abs(sy-ty)){
        ans = abs(sy-ty);
    }else{
        ans = abs(sx-tx)/2 - abs(sy-ty)/2 + abs(sy-ty);
    }
    
    cout << ans << endl;
    return 0;
}

D: Avoid K Palindrome

解法

• 動的計画法 (DP)
• $\text{dp} [i][s]$ := $i$ 文字目まで決定して、直前の長さ $K - 1$ の文字列が $s$ である場合の数
  • 文字列を状態として持つ
• map<string, long long int> で管理する

ABC359D.cpp

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

bool kaibun(string s){
    string s2 = s;
    reverse(s2.begin(), s2.end());
    return s == s2;
}

int main(){
    const int MOD = 998244353;

    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    map<string, long long int> dp;
    dp[""] = 1;
    for(int i=0; i<n; i++){
        map<string, long long int> tmp;
        swap(tmp, dp);
        for(auto [t, num] : tmp){
            for(char c='A'; c<='B'; c++){
                if(s[i]!='?' && s[i]!=c){
                    continue;
                }

                string t2 = t + c;

                if(t2.size()==k && kaibun(t2)){
                    continue;
                }

                if(t2.size()==k){
                    t2.erase(t2.begin());
                }

                dp[t2] += num % MOD;
                dp[t2] %= MOD;
            }
        }
    }

    long long int ans = 0;
    for(auto [t, num] : dp){
        ans += num;
        ans %= MOD;
    }

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