LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 424

Last updated at Posted at 2025-09-23

A - Isosceles

問題文

三角形の公式の問題です。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(a == b || b == c || c == a){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

B - Perfect

問題文
どのユーザーがどのコンテストのどの問題を正解したか保持をします。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> ans(n);
    rep(i, k){
        int a, b;
        cin >> a >> b;
        a--; b--;
        ans[a].push_back(b);
        if(ans[a].size() >= m){
            cout << a + 1 << ' ';
        }
    }
    cout << endl;
    return 0;
}

C - New Skill Acquired

問題文

問題文を読むと有向グラフであるグラフ問題だと分かります。
今回はbfsで回答しましょう。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n;
    cin >> n;
    queue<int> que;
    vector<vector<int>> sk(n+1);
    rep(i, n){
        int a, b;
        cin >> a >> b;
        if(a == 0 && b == 0){
            que.push(i+1);
        }else{
            sk[a].push_back(i+1);
            sk[b].push_back(i+1);
        }
    }

    vector<bool> used(n+1);
    while(que.size()){
        int s = que.front();
        que.pop();

        if(used[s]) continue;
        used[s] = true;

        for(auto i:sk[s]){
            if(!used[i]) que.push(i);
        }
    }
    int ans = 0;
    for(auto u:used) if(u) ans++;
    cout << ans << endl;

    return 0;
}

D - 2x2 Erasing 2

問題文

7*7のマスにて、白か黒かを探索していきます。
2^49はTLEになります。
枝刈りをしましょう。

7*7のマスで9マスだけの判定で良いのが分かります。
４マスごとに判定していくので、4^9まで計算量を落とせます。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

void solve(){
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    int ans = 9;
    auto dfs = [&](auto dfs, int now)->void{

        rep(y, h-1) rep(x,w-1){
            int cnt = 0;
            rep(dy, 2){
                rep(dx, 2){
                    int xx = x + dx;
                    int yy = y + dy;
                    if(s[yy][xx] == '#') cnt++;
                }
            }
            if(cnt == 4){
                rep(dx, 2){
                    int xx = x + dx;
                    int yy = y + 1;
                    s[yy][xx] = '.';
                    dfs(dfs, now+1);
                    s[yy][xx] = '#';
                }
                return;
            }
        }

        ans = min(ans, now);
    };
    dfs(dfs, 0);
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t){
        solve();
    }
    return 0;
}

E - Cut in Half

問題文

一番長い棒を半分の大きさにします。
K回繰り返します。
x番目の棒を長さを求めてください。

プライオリティーキューの問題です。
棒を切ってプライオリティーキューに入れるだけの問題です。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

void solve(){
    int n, k, x;
    cin >> n >> k >> x;
    priority_queue<pair<double, int>, vector<pair<double, int>>, less<pair<double, int>>> que;
    rep(i, n){
        int a;
        cin >> a;
        que.emplace(a, 1);
    }

    while(k>0){
        auto [a, c] = que.top();
        que.pop();

        if(k < c){
            que.emplace(a, c-k);
            c = k;
        }

        k -= c;
        que.emplace(a / 2, c * 2);
    }

    while(x > 0){
        auto [a, c] = que.top();
        que.pop();
        x -= c;
        if(x <= 0){
            cout << fixed_setprecision(10) << a << endl;
            return;
        }
    }
}

int main() {
    int t;
    cin >> t;
    rep(i, t) solve();
    return 0;
}

F - Adding Chords

F - Adding Chords

セグメント木、Fenwick 木（BIT）の問題です。
今回はセグメント木で解きます。
同一の区間に交差がないかをhashを保持してxorで判定をしています。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int nn;
unsigned long long dat[2000010 * 2];

void init(int n_){
    nn = 1;
    while(nn < n_) nn *= 2;
    for(int  i=0; i < 2 * nn - 1; i++) dat[i] = 0;
}

void update(int k, unsigned long long a){
    k += nn - 1;
    dat[k] ^= a;
    while(k > 0){
        k = (k - 1) / 2;
        dat[k] = dat[k * 2 + 1] ^ dat[k * 2 + 2];
    }
}

unsigned long long query(int a, int b, int k, int l, int r){
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b) return dat[k];
    else{
        unsigned long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        unsigned long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return vl ^ vr;
    }
}

int main() {
    random_device seed_gen;
    mt19937_64 rnd(seed_gen());
    int n, q;
    cin >> n >> q;

    init(n);

    rep(i, q){
        int l, r;
        cin >> l >> r;
        if(query(0, l+1, 0, 0, nn) == query(0, r+1, 0, 0, nn)){
            cout << "Yes" << endl;
            unsigned long long x = rnd();
            update(l, x);
            update(r, x);
        }else{
            cout << "No" << endl;
        }
    }

    return 0;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?