【ABC343】AtCoder Beginner Contest 343【C++】

コンテスト名

AtCoder Beginner Contest 343

コンテストURL

https://atcoder.jp/contests/abc343

開催日

2024/03/02 21:00-22:40

---

A: Wrong Answer

解法

• 問題文通りに実装する

ABC343A.cpp

#include <iostream>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    for(int i=0; i<=9; i++){
        if(i!=(a+b)){
            cout << i << endl;
            return 0;
        }
    }
}

B: Adjacency Matrix

解法

• 2次元配列 vector<vector<int>> に格納して順に出力する

ABC343B.cpp

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

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

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

    return 0;
}

C: 343

解法

• 全探索
• $N$ 以下の立方数は $O(\sqrt[3]{N})$ 個
  • $x^3 = K$ の $K$ ではなく $x$ を全探索する
• 立方数を降順で回文判定する

ABC343C.cpp

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

bool kaibun(string s){
    for(int i=0; i<s.size()/2; i++){
        if(s[i]!=s[s.size()-1-i]){
            return false;
        }
    }
    return true;
}

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

    for(long long int i=1e6; i>=1; i--){
        long long int x = i*i*i;
        if(x<=n){
            string s = to_string(x);
            if(kaibun(s)){
                cout << x << endl;
                return 0;
            }
        }
    }
}

D: Diversity of Scores

解法

• 種類数の変動は毎秒 -1, 0, +1 のいずれか
• 各選手の現在の得点を vector<long long int> で管理する
• 得点種類別の人数を unordered_map<long long int, int> で管理する

ABC343D.cpp

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

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

    vector<long long int> V(n);
    unordered_map<long long int, int> M;
    M[0] = n;
    int cnt = 1;
    int a, b;
    for(int i=0; i<t; i++){
        cin >> a >> b;
        a--;
        if(M[V[a]]==1){
            cnt--;
        }
        M[V[a]]--;
        V[a] += b;
        M[V[a]]++;
        if(M[V[a]]==1){
            cnt++;
        }

        cout << cnt << endl;
    }

    return 0;
}

E: 7x7x7

解法

• 全探索
• 立方体を 1 つ固定してそのほかの 2 つの立方体を全探索する
  • $(0, 0, 0)$ に固定
  • 全探索範囲を [0, 7] にすると考慮できない配置があるため [-7, 7] の範囲で全探索する
• 包除原理で体積を求める
  • $v_3 = C_1 \cap C_2 \cap C_3$
  • $v_2 = (C_1 \cap C_2) + (C_2 \cap C_3 )+ (C_3 \cap C_1) -3v_3$
  • $v_1 = 3 × 7^3 - 2v_2 - 3v_3$
• 共通部分の直方体の各辺の長さは $max \lbrace 0, min \lbrace a_i + 7, a_j + 7 \rbrace - max \lbrace a_i, a_j \rbrace \rbrace$ で求められる

ABC343E.cpp

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

int main(){
    int v1, v2, v3;
    cin >> v1 >> v2 >> v3;

    int a1 = 0, b1 = 0, c1 = 0;
    int x1, x2, x3;
    for(int a2=-7; a2<=7; a2++){
        for(int b2=-7; b2<=7; b2++){
            for(int c2=-7; c2<=7; c2++){
                for(int a3=-7; a3<=7; a3++){
                    for(int b3=-7; b3<=7; b3++){
                        for(int c3=-7; c3<=7; c3++){
                            x3 = 1;
                            x3 *= max(0, min({a1, a2, a3}) + 7 - max({a1, a2, a3}));
                            x3 *= max(0, min({b1, b2, b3}) + 7 - max({b1, b2, b3}));
                            x3 *= max(0, min({c1, c2, c3}) + 7 - max({c1, c2, c3}));

                            x2 = 0;
                            x2 += max(0, min(a1, a2) + 7 - max(a1, a2))*max(0, min(b1, b2) + 7 - max(b1, b2))*max(0, min(c1, c2) + 7 - max(c1, c2));
                            x2 += max(0, min(a2, a3) + 7 - max(a2, a3))*max(0, min(b2, b3) + 7 - max(b2, b3))*max(0, min(c2, c3) + 7 - max(c2, c3));
                            x2 += max(0, min(a3, a1) + 7 - max(a3, a1))*max(0, min(b3, b1) + 7 - max(b3, b1))*max(0, min(c3, c1) + 7 - max(c3, c1));
                            x2 -= 3*x3;

                            x1 = 3*7*7*7 - 2*x2 - 3*x3;

                            if(x1==v1 && x2==v2 && x3==v3){
                                cout << "Yes" << endl;
                                cout << a1 << " " << b1 << " " << c1 << " " << a2 << " " << b2 << " " << c2 << " " << a3 << " " << b3 << " " << c3 << endl;
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }
    
    cout << "No" << endl;
    return 0;
}