AtCoder Beginner Contest 410

A - G1

問題文

O(N)
ループ文の問題です。
KがA_i以下の数を探索します。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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, k;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    cin >> k;

    int ans = 0;
    rep(i, n){
        if(a[i] >= k) ans++;
    }
    cout << ans << endl;

    return 0;
} 

B - Reverse Proxy

問題文

O(n+q)
全探索の問題です。
2重ループで探索できます。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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, q;
    cin >> n >> q;
    vector<int> x(q);
    rep(i, q) cin >> x[i];

    vector<int> box(n);
    rep(i, q){
        if(x[i]>0){
            box[x[i]-1]++;
            cout << x[i];
        }else{
            int t = 1e9;
            int m = 0;
            rep(j, n){
                if(box[j] < t){
                    t = box[j];
                    m = j;
                }
            }
            box[m]++;
            cout << m + 1;
        }

        if(i - 1 < q) cout << ' ';
    }
    cout << endl;

    return 0;
} 

C - Rotatable Array

問題文

O(N)
全探索、オフセットの問題です。
タイプ3のクエリの時、何回ローテートさせたかoffset変数に保持をしておきます。
offset%nで現在の位置を特定します。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, n) a[i] = i+1;
    int offset = 0;

    rep(i, q){
        int t;
        cin >> t;
        
        if(t == 1){
            int p, x;
            cin >> p >> x;
            a[(offset + p - 1) % n] = x;
        }
        if(t == 2){
            int p;
            cin >> p;
            cout << a[(offset + p - 1) % n] << endl;
        }
        if(t == 3){
            int k;
            cin >> k;
            offset = (offset + k) % n;
        }
    }

    return 0;
} 

D - XOR Shortest Walk

問題文

全探索の問題です。
dfs、bfs、dpでも解けます。
1からNまでを探索します。
グラフは有向グラフです。
各辺に重みがあり、xorで計算した合計の値が最も小さい値を求めます。

通常のdfsだと一度通った道をbool型で判定します。

C++

vector<bool> used(n);

auto dfs = [&](auto dfs, int u, int wxor){
    if(u >= n-1){
        ans = min(ans, wxor);
    }
    if(used[u]) return;
    used[u] = true;
    for(auto [v, w]:graph[u]){
        dfs(dfs, v, wxor ^ w);
    }
};

今回は同じ頂点を２回通ることがあります。
その時、同じ頂点を同じxorの合計で通過するか判定します。
通過していた場合、処理の終了を行います。
頂点倍加と呼ばれる典型のテクニックです。

C++

map<pair<int, int>, bool> used(n);

auto dfs = [&](auto dfs, int u, int wxor){
    if(u >= n-1){
        ans = min(ans, wxor);
    }
    if(used[{u, wxor}]) return;
    used[{u, wxor}] = true;
    for(auto [v, w]:graph[u]){
        dfs(dfs, v, wxor ^ w);
    }
};

考察が終了しました。
コーディングしましょう。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#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;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);
    rep(i, m){
        int a, b;
        int w;
        cin >> a >> b >> w;
        a --; b--;
        graph[a].push_back({b, w});
    }

    map<P, bool> used;
    int ans = 1e9;

    auto dfs = [&](auto dfs, int u, int wxor){
        if(u >= n-1){
            ans = min(ans, wxor);
        }
        if(used[{u, wxor}]) return;
        used[{u, wxor}] = true;
        for(auto [v, w]:graph[u]){
            dfs(dfs, v, wxor ^ w);
        }
    };

    dfs(dfs, 0, 0);
    
    if(ans == 1e9) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
} 

すぬけさんの解説動画の勉強中です。追記をします。