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 470

0
Last updated at Posted at 2026-08-09

A - Fizz

問題文

FizzBuzzの問題です。
i%3==0の時だけ出力をFizzにしましょう。

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;

    rep(i, n){
        int m = i+1;
        if(m%3 == 0) cout << "Fizz" << endl;
        else cout << m << endl;
    }

    return 0;
}

B - Monocolor

問題文

データ構造の問題です。
最も色が多いカラーを探索します。
n-max_colorの値が答えになります。

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;
    vector<int> c(n);
    rep(i, n) cin >> c[i];
    map<int, int> mp;
    rep(i, n) mp[c[i]]++;
    int cnt = 0;
    for(auto [color, num]:mp){
        cnt = max(cnt, num);
    }
    cout << n - cnt << endl;
    return 0;
}

C - Inc, Dec, Xor

問題文

O(N+Q)
クエリ2の時に配列aを全て探索して1以上の値の要素をxor、-1、xorを行うとTLEになります。
下記は最初にコーディングした全探索です。

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, q;
    cin >> n >> q;
    vector<int> a(n);
    int ans = 0;
    rep(i, q){
        int query;
        cin >> query;

        if(query == 1){
            int x;
            cin >> x;
            ans ^= a[x-1];
            a[x-1]++;
            ans ^= a[x-1];
        }

        if(query == 2){
            rep(j, n){
                if(a[j]){
                    ans ^= a[j];
                    a[j]--;
                    ans ^= a[j];
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}

クエリ2の時にO(N^2)となっているのが問題です。
要素が1以上のindexを別で管理すると解決します。
問題文に、

2：i=1,2,…,N に対し、Ai≥1ならばAiの値を1減らす。

とあります。
クエリ2の時に、要素が-1されるのでO(N+q)になるのとわかります。
私はsetでindexを管理しました。

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, q;
    cin >> n >> q;
    vector<int> a(n);
    set<int> st;
    int ans = 0;
    rep(i, q){
        int query;
        cin >> query;

        if(query == 1){
            int x;
            cin >> x;
            ans ^= a[x-1];
            a[x-1]++;
            ans ^= a[x-1];
            st.insert(x-1);
        }

        if(query == 2){
            auto it = st.begin();
            while(it != st.end()){
                int v = *it;
                ans ^= a[v];
                a[v]--;
                ans ^= a[v];
                if(a[v] == 0){
                    it = st.erase(it);
                }else{
                    it++;
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}

D - Inverse and Swap

問題文

値とindexを別々の配列で管理する問題です。
コンテスト中は詰めきれずに実装できませんでした。
テストケースの1で考察します。

5 5
2 1 3 5 4
1 2 4
2
1 2 3
1 3 4
2

クエリの1 2 4と2を追うと

2 5 3 1 4
4 1 3 5 2

と変化します。
ここからクエリ２は値とindexを逆転させる処理だと分かります。
値とindexを別々の配列で管理して値を追っていきましょう。
値の配列の変化を記載します。

2 1 3 5 4
2 5 3 1 4
2 5 3 1 4
3 5 2 1 4
4 5 2 1 3

と変化した時、indexの配列は、

2 1 3 5 4
4 1 3 5 2
4 1 3 5 2
4 3 1 5 2
4 3 5 1 2

と変化します。
つまりクエリ1の時に値とindexのどちらが基準になっているか判定して配列の要素を交換します。
基準になっている配列の値を保持します。
x, yから配列の値を交換します。
基準になっていない配列のindexのxの値とindexのyの値を交換すると上手くいきます。

C++
        if(query == 1){
            int x, y;
            cin >> x >> y;
            x--; y--;
            int xx = p[k][x];
            int yy = p[k][y];
            int kk = k ^ 1;
            swap(p[k][x], p[k][y]);
            swap(p[kk][xx], p[kk][yy]);
        }

クエリ2は値とindexのどちらが基準になっているか判定して保持します。
コーディングしましょう。

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, q;
    cin >> n >> q;
    vector<vector<int>> p(2, vector<int>(n, 0));
    rep(i, n) cin >> p[0][i], p[0][i]--;
    rep(i, n) p[1][p[0][i]] = i;

    int k = 0;
    rep(i, q){
        int query;
        cin >> query;

        if(query == 1){
            int x, y;
            cin >> x >> y;
            x--; y--;
            int xx = p[k][x];
            int yy = p[k][y];
            int kk = k ^ 1;
            swap(p[k][x], p[k][y]);
            swap(p[kk][xx], p[kk][yy]);
        }
        if(query == 2){
            k = k ^ 1;
        }
    }

    rep(i, n){
        cout << p[k][i] + 1;
        if(i < n - 1) cout << ' ';
        else  cout << 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?