【ABC361】AtCoder Beginner Contest 361【C++】

コンテスト名

デンソークリエイトプログラミングコンテスト2024（AtCoder Beginner Contest 361）

コンテストURL

開催日

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

---

A: Insert

解法

• 順番に出力する
  • 正数列 $A$ の $K$ 要素目まで出力する
  • 整数 $X$ を出力する
  • 正数列 $A$ の $K + 1$ 要素目から $N$ 要素目まで出力する

ABC361A.cpp

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

int main(){
    int n, k, x;
    cin >> n >> k >> x;

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

    for(int i=0; i<k; i++){
        if(i){
            cout << " ";
        }
        cout << A[i];
    }

    cout << " " << x;

    for(int i=k; i<n; i++){
        cout << " " << A[i];
    }

    cout << endl;
    return 0;
}

B: Intersection of Cuboids

解法

• 共通部分をもつ条件を考える
  • 以下の 3 式がすべて成り立つとき共通部分をもつ
  • $\text{min}(d, j) - \text{max}(a, g) > 0$
  • $\text{min}(e, k) - \text{max}(b, h) > 0$
  • $\text{min}(f, l) - \text{max}(c, i) > 0$
• 共通部分をもたない条件を考える
  • 以下の 3 式のいずれかが成り立つとき共通部分をもたない
  • $x$ 軸方向に重ならないとき $d \leqq g \ \text{OR}\ a \geqq j$
  • $y$ 軸方向に重ならないとき $e \leqq h \ \text{OR}\ b \geqq k$
  • $z$ 軸方向に重ならないとき $f \leqq i \ \text{OR}\ c \geqq l$
• 十字に重なるパターン注意する

ABC361B_1.cpp

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

int main(){
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;

    int g, h, i, j, k, l;
    cin >> g >> h >> i >> j >> k >> l;

    if((min(d, j)-max(a, g))>0 && (min(e, k)-max(b, h))>0 && (min(f, l)-max(c, i))>0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

ABC361B_2.cpp

#include <iostream>
using namespace std;

int main(){
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;

    int g, h, i, j, k, l;
    cin >> g >> h >> i >> j >> k >> l;

    if(d<=g || a>=j){
        cout << "No" << endl;
        return 0;
    }
    if(e<=h || b>=k){
        cout << "No" << endl;
        return 0;
    }
    if(f<=i || c>=l){
        cout << "No" << endl;
        return 0;
    }

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

C: Make Them Narrow

解法

• 昇順にソートしてから探索する
• ソートした数列 $A$ について $A_{i+N-K-1} - A_i$ の最小値を求める
  • ソートした数列 $A$ の連続する $N - K$ 要素を残すのが最適である

ABC361C.cpp

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

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

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

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

    int minv = 1e9;
    for(int i=0; i<=k; i++){
        minv = min(minv, A[i+n-k-1]-A[i]);
    }

    cout << minv << endl;
    return 0;
}

D: Go Stone Puzzle

解法

• 状態を頂点としたグラフを考えて幅優先探索 (BFS) する
  • スタートを文字列 $S$ 、ゴールを文字列 $T$ として幅優先探索する
• map<string, int> で状態までの操作回数、queue<pair<string, int>> で状態と空きマスの位置を管理する

ABCxxxD.cpp

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

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

    s += "..";
    t += "..";

    map<string, int> dist;
    queue<pair<string, int>> Q;
    dist[s] = 0;
    Q.emplace(s, n);
    while(!Q.empty()){
        auto [now, k] = Q.front();
        Q.pop();

        for(int i=0; i<n+2-1; i++){
            if(now[i]=='.' || now[i+1]=='.'){
                continue;
            }

            string next = now;

            next[k] = now[i];
            next[k+1] = now[i+1];
            next[i] = '.';
            next[i+1] = '.';

            if(dist.count(next)){
                continue;
            }

            dist[next] = dist[now] + 1;
            Q.emplace(next, i);
        }
    }

    if(dist.count(t)){
        cout << dist[t] << endl;
    }else{
        cout << -1 << endl;
    }
    
    return 0;
}