【ABC390】AtCoder Beginner Contest 390【C++】

コンテスト名

AtCoder Beginner Contest 390

コンテストURL

https://atcoder.jp/contests/abc390

開催日

2025/01/25 21:00-22:40

---

A: 12435

解法

• 入れ替える隣り合う 2 つの項を全探索して判定する

ABC390A.cpp

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

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

    for(int i=0; i<4; i++){
        vector<int> B = A;
        swap(B[i], B[i+1]);
        bool flag = true;
        for(int j=0; j<5; j++){
            if(B[j]!=j+1){
                flag = false;
                break;
            }
        }
        if(flag){
            cout << "Yes" << endl;
            return 0;
        }
    }

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

B: Geometric Sequence

解法

• すべての $ii$ において、 $\frac{A_{i+1}}{A_i} = \frac{A_2}{A_1}$ を満たしているかを判定する
• 小数を使わずに済むように、 $A_{i+1} \times A_1 = A_2 \times A_i$ で判定する

ABC390B.cpp

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

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

    for(int i=0; i<n-1; i++){
        if(A[i+1]*A[0]!=A[1]*A[i]){
            cout << "No" << endl;
            return 0;
        }
    }

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

C: Paint to make a rectangle

解法

• 縦、横について、黒く塗られているマスのうち、最小の座標と最大の座標をそれぞれ求める
• 求めた長方形のなかに、白く塗られているマスがないかを判定する

ABC390C.cpp

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

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

    vector<vector<char>> G(h, vector<char>(w));
    char c;
    int xmin = h, xmax = -1, ymin = w, ymax = -1;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> c;
            G[i][j] = c;
            if(c=='#'){
                xmin = min(xmin, i);
                xmax = max(xmax, i);
                ymin = min(ymin, j);
                ymax = max(ymax, j);
            }
        }
    }

    for(int i=xmin; i<=xmax; i++){
        for(int j=ymin; j<=ymax; j++){
            if(G[i][j]=='.'){
                cout << "No" << endl;
                return 0;
            }
        }
    }

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

D: Stone XOR

解法

• 再帰関数、深さ優先探索 (DFS)
• 袋をグループ分けすることを考える
  • グループ分けの組み合わせが重複しないように、現在あるグループに入るのか、新たなグループを作るのかを $i$ の順に探索する
  • グループ数は最大 $N$ 、最小 1 となる

ABC390D.cpp

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

int n;
unordered_set<long long int> S;
vector<long long int> A;

void f(int len, vector<long long int> &V){
    if(len==n){
        long long int sum = 0;
        for(int i=0; i<V.size(); i++){
            sum ^= V[i];
        }

        S.insert(sum);
        
        return;
    }

    for(int i=0; i<V.size(); i++){
        V[i] += A[len];
        f(len+1, V);
        V[i] -= A[len];
    }
    V.push_back(A[len]);
    f(len+1, V);
    V.pop_back();
}

int main(){
    cin >> n;

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

    vector<long long int> a;
    f(0, a);

    cout << S.size() << endl;

    return 0;
}