【ABC395】AtCoder Beginner Contest 395【C++】

コンテスト名

AtCoder Beginner Contest 395

コンテストURL

https://atcoder.jp/contests/abc395

開催日

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

---

A: Strictly Increasing?

解法

• 問題文通りに判定する

ABC395A.cpp

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

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

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

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

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

B: Make Target

解法

• 問題文通りに実装する

ABC395B.cpp

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

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

    vector<vector<char>> G(n, vector<char>(n));
    for(int i=0; i<n; i++){
        int j = n + 1 - i - 2;

        if(i>j){
            continue;
        }

        if(i%2==0){
            for(int a=i; a<=j; a++){
                for(int b=i; b<=j; b++){
                    G[a][b] = '#';
                }
            }
        }else{
            for(int a=i; a<=j; a++){
                for(int b=i; b<=j; b++){
                    G[a][b] = '.';
                }
            }
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << G[i][j];
        }
        cout << '\n';
    }

    return 0;
}

C: Shortest Duplicate Subarray

解法

• map<int, int> に各値の直近の出現位置を記録する

ABC395C.cpp

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

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

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

    map<int, int> M;
    int minv = n + 1;
    for(int i=0; i<n; i++){
        if(M.count(A[i])){
            minv = min(minv, i-M[A[i]]+1);
        }

        M[A[i]] = i;
    }

    if(minv>n){
        cout << -1 << endl;
    }else{
        cout << minv << endl;
    }

    return 0;
}

D: Pigeon Swap

解法

• 3 つの vector<int> に記録し、巣にいる鳩をすべて移動させる種類 2 の操作に対応する

ABC395D.cpp

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

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

    vector<int> H(n), V(n), S(n);
    for(int i=0; i<n; i++){
        H[i] = i;
        V[i] = i;
        S[i] = i;
    }

    int num, a, b;
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            cin >> a >> b;
            a--;
            b--;
            
            H[a] = V[b];
        }else if(num==2){
            cin >> a >> b;
            a--;
            b--;
            
            swap(V[a], V[b]);
            swap(S[V[a]], S[V[b]]);
        }else if(num==3){
            cin >> a;
            a--;

            cout << S[H[a]]+1 << '\n';
        }
    }
}