Zenn
🔵

【ABC349】AtCoder Beginner Contest 349【C++】

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

コンテスト名

AtCoder Beginner Contest 349

コンテストURL

https://atcoder.jp/contests/abc349

開催日

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

A: Zero Sum Game

解法

  • N 人の持ち点の総和は 0 になる
  • N - 1 人までの総和を求めて符号を変える
ABC349A.cpp
#include <iostream>
using namespace std;

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

   int sum = 0, a;
   for(int i=0; i<n-1; i++){
        cin >> a;
        sum += a;
   }

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

B: Commencement

解法

  • unordered_map を 2 回用いる
    • unordered_map<char, int> で各文字の登場回数を記録する
    • unordered_map<int, int> で各登場回数の文字数を記録する
ABC349B.cpp
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

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

    unordered_map<char, int> M;
    for(int i=0; i<s.size(); i++){
        M[s[i]]++;
    }

    unordered_map<int, int> M2;
    for(auto [c, cnt] : M){
        M2[cnt]++;
    }

    for(auto [c, cnt] : M2){
        if(cnt!=2){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

C: Airport Code

解法

  • 文字列 T をすべて小文字に変換してから比較する
    • transform(T.begin(), T.end(), T.begin(), ::tolower)
  • 文字列 T の 3 文字目（最後の文字）が X ならば T の最初の 2 文字が 文字列 S の部分列かを判定する
  • 文字列 T の 3 文字目（最後の文字）が X でないならば T が 文字列 S の部分列かを判定する
ABC349C.cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

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

    transform(t.begin(), t.end(), t.begin(), ::tolower);

    int cnt = 0;
    for(int i=0; i<s.size(); i++){
        if(s[i]==t[cnt]){
            cnt++;
        }
    }

    if(t[2]=='x' && cnt>=2){
        cout << "Yes" << endl;
        return 0;
    }else if(cnt>=3){
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;
    return 0;
}

D: Divide Interval

解法

  1. 再帰関数
    • 「良い数列」 S(l, r) と数列 S(L, R) との連続共通部分列の最適な分割を f(l, r, L, R) とする
    • S(l, r) が S(L, R) に含まれる場合は S(l, r) を返す
    • S(l, r) が S(L, R) に含まれない場合は 3 つの場合を考える
      • mid = \frac{l + r}{2} とする
      • S(L, R) が S(l, mid) に含まれる場合は f(l, mid, L, R) を返す
      • S(L, R) が S(mid, r) に含まれる場合は f(mid, r, L, R) を返す
      • S(L, R) が S(l, mid) と S(mid, r) の両方にまたがって含まれる場合は f(l, mid, L, R) と f(mid, r, L, R) を連結したものを返す
    • f(0, 2^{60}, L, R) が求める答え
  2. 左端から順番に貪欲に分割する
    • 左端 l のとき最大の分割は l を割り切れる最大の 2 のべき乗 2^{i} とすると S(l, l + 2^{i}) = S(2^{i} j, 2^{i} (j + 1))
    • l \equiv 0 \pmod {2^{i}} かつ l + 2^{i} \leqq R を満たす最大の i を求める
ABC349D_1.cpp
#include <iostream>
#include <vector>
using namespace std;

vector<pair<long long int, long long int>> f(long long int l, long long int r, long long int L, long long int R){
    if(l>=L && r<=R){
        return {{l, r}};
    }

    long long int mid = (l + r)/2;
    if(R<=mid){
        return f(l, mid, L, R);
    }else if(mid<=L){
        return f(mid, r, L, R);
    }

    vector<pair<long long int, long long int>> left_result = f(l, mid, L, R);
    vector<pair<long long int, long long int>> right_result = f(mid, r, L, R);
    left_result.insert(left_result.end(), right_result.begin(), right_result.end());
    return left_result;
}

int main(){
    long long int l, r;
    cin >> l >> r;

    vector<pair<long long int, long long int>> ans = f(0, 1LL<<60, l, r);

    cout << ans.size() << endl;
    for(auto [l, r] : ans){
        cout << l << " " << r << '\n';
    }

    return 0;
}
ABC349D_2.cpp
#include <iostream>
#include <vector>
using namespace std;

int main(){
    long long int l, r;
    cin >> l >> r;

    vector<pair<long long int, long long int>> ans;
    while(l<r){
        int i = 0;
        while((l%(1LL<<(i+1))==0) && ((l+(1LL<<(i+1)))<=r)){
            i++;
        }
        ans.emplace_back(l, l+(1LL<<i));
        l += (1LL<<i);
    }

    cout << ans.size() << endl;
    for(auto [l, r] : ans){
        cout << l << " " << r << '\n';
    }
    return 0;
}

E: Weighted Tic-Tac-Toe

解法

  • 再帰関数
  • 盤面 G の状態からゲームをしたときの勝者を f(G) とする
  • G が終了状態ならば勝敗を判定する
  • G が終了状態でないならば G から 1 回で遷移できる各盤面 G' について f(G') を求める
  • 相手の評価値を負の値として自分の評価値に反映させる
    • 相手の評価値が大きいほど自分の評価値は小さくなる
    • 自分が選んだマスの得点を加えることで自分にとって有利なマスを選ぶ
  • 盤面をキーとしてメモ化再帰
ABC349E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

vector<vector<int>> A(3, vector<int>(3));
vector<vector<int>> G(3, vector<int>(3));
map<vector<vector<int>>, long long int> M;

bool check(){
	for(int i=0; i<3; i++){
		bool flag = true;
		for(int j=1; j<3; j++){
			if(G[i][j]!=G[i][0]){
                flag = false;
            }
		}
		if(G[i][0]==0){
            flag = false;
        }
		if(flag){
            return true;
        }
	}

    for(int i=0; i<3; i++){
		bool flag = true;
		for(int j=1; j<3; j++){
			if(G[j][i]!=G[0][i]){
                flag = false;
            }
		}
		if(G[0][i]==0){
            flag = false;
        }
		if(flag){
            return true;
        }
	}
	
	if(G[0][0]==G[1][1] && G[0][0]==G[2][2] && G[0][0]!=0){
        return true;
    }
	if(G[0][2]==G[1][1] && G[0][2]==G[2][0] && G[0][2]!=0){
        return true;
    }
	
	return false;
}

long long int dfs(int player){
	if(check()){
        return -1e18;
    }

    if(M.count(G)){
        return M[G];
    }

	long long int ans = -1e18;
    bool flag = true;

	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			if(!G[i][j]){
				G[i][j] = player;
				ans = max(ans, -dfs(player^3) + A[i][j]);
				G[i][j] = 0;
				flag = false;
			}
		}
	}

	if(flag){
        ans = 0;
    }
    
	return M[G] = ans;
}

int main(){
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			cin >> A[i][j];
		}
	}
	
	long long int ans = dfs(1);
	
	if(ans>0){
        cout << "Takahashi" << endl;
    }else{
        cout << "Aoki" << endl;
    }
	
	return 0;
}

Discussion