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 396

Last updated at Posted at 2025-03-09

A - Triple Four

O(N)
forループの問題です。

a_i = a_{i+1} = a_{i+2}

が成立した時にYesを出力します。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    rep(i, N-2){
        if(A[i] == A[i+1] && A[i+1] == A[i+2]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}

B - Card Pile

O(N)
全探索の問題です。
タイプ1 : 整数xの書かれたカードを1枚カードの山の一番上に積み重ねる。
とあるので、問題文通りに0のデータを100枚ほどデータ構造へ追加します。
データ構造は、山の一番上とあるのでstackを使用します。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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 Q;
    cin >> Q;
    stack<int> st;
    rep(i, 100) st.push(0);
    rep(i, Q){
        int op;
        cin >> op;
        if(op == 1){
            int x;
            cin >> x;
            st.push(x);
        }
        if(op == 2){
            cout << st.top() << endl;
            st.pop();
        }
    }

    return 0;
}

C - Buy Balls

O(N)
貪欲法の問題です。
黒色のボールの個数が白色のボールの個数以上になるようにボールを0個以上選ぶとき、
とあり、白色のボールの個数を先に探索する必要があります。

B_i + W_i >= 0 

W_i >= 0

この２つの条件を満たす時、白色のボールを選んで良いです。
黒色のボールの個数は、まず白色のボールの個数と同じ数だけ選びます。
さらに、

B_i >= 0

の条件を満たす要素を探索します。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    cin >> N >> M;
    vector<ll> B(N), W(M);
    rep(i, N) cin >> B[i];
    rep(i, M) cin >> W[i];
    sort(B.begin(), B.end());
    reverse(B.begin(), B.end());
    sort(W.begin(), W.end());
    reverse(W.begin(), W.end());

    ll ans = 0;
    int K = min(N, M);
    int cnt = 0;
    rep(i, K){
        if(W[i] >= 0 && B[i] + W[i] >= 0){
            ans += W[i];
            cnt++;
        }
    }
    rep(i, N){
        if(i < cnt || B[i] >= 0){
            ans += B[i];
        }
    }
    cout << ans << endl;

    return 0;
}

もっと綺麗にコーディングできないか考察しましょう。

C++
    ll ans = 0;
    ll sumb = 0;
    ll maxw = 0, sumw = 0;
    rep(i, N){
        // Bの要素の合計
        sumb += B[i];
        // Wの要素の合計
        if(i < M) sumw += W[i];
        maxw = max(maxw, sumw);
        // Bの合計とWの合計の最大値を加算した最大値を求める
        ans = max(ans, sumb+maxw);
    }
    cout << ans << endl;

すぬけさんのコードはいつみても綺麗ですね。
コンテスト中に自分のコードは誤っていると思いましたが、このコードに辿りつきませんでした。
下記が整理したコードです。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    cin >> N >> M;
    vector<ll> B(N), W(M);
    rep(i, N) cin >> B[i];
    rep(i, M) cin >> W[i];
    sort(B.rbegin(), B.rend());
    sort(W.rbegin(), W.rend());

    ll ans = 0;
    ll sumb = 0;
    ll maxw = 0, sumw = 0;
    rep(i, N){
        sumb += B[i];
        if(i < M) sumw += W[i];
        maxw = max(maxw, sumw);
        ans = max(ans, sumb+maxw);
    }
    cout << ans << endl;

    return 0;
}

D - Minimum XOR Path

O(N!)
グラフの問題です。
頂点Nに、M個の辺を探索する最大の計算量は、

10! = 3628800

全探索で間に合います。
xorと書かれていて難しそうに見えますが要領は加算と同じです。
この時点で順列全探索とDFSの選択肢が見えます。
今回はDFSを選択しましょう。

・現在、通過した頂点を配列usedで管理する
・dfs関数の呼び出し前にxorでコストを計算、dfs関数の呼び出し後にxorでコストを計算

ここまで考察できたのでコーディングします。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    cin >> N >> M;
    vector<vector<pair<int, ll>>> graph(N);
    rep(i, M){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        u--; v--;

        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    ll ans = 2e18;
    vector<bool> used(N);
    auto dfs = [&](auto dfs, int u, ll num){
        if(u == N-1){
            ans = min(ans, num);
            return;
        }

        used[u] = true;

        for(auto [v, w]:graph[u]){
            if(used[v]) continue;
            num ^= w;
            dfs(dfs, v, num);
            num ^= w;
        }

        used[u] = false;
    };

    dfs(dfs, 0, 0);

    cout << ans << 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?