LoginSignup
1
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 402

Posted at

A - CBC

O(N)
文字列の大文字だけ出力します。
A=65、Z=90です。

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() {
    string S;
    cin >> S;

    int N = S.size();
    rep(i, N){
        if(65 <= S[i] && S[i] <= 90){
            cout << S[i];
        }
    }
    cout << endl;

    return 0;
}

B - Restaurant Queue

O(N)
データ構造、キューの問題です。

  • questが1の時、キューにxを追加します
  • questが2の時、キューの先頭を表示して、popします
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 Q;
    cin >> Q;

    queue<int> que;
    rep(i, Q){
        int q;
        cin >> q;

        if(q==1){
            int x;
            cin >> x;
            que.push(x);
        }

        if(q==2){
            int x = que.front();
            que.pop();
            cout << x << endl;
        }
    }

    return 0;
}

C - Dislike Foods

O(N+M+ΣK_i)?
よくわからないです。

自分の解放ではO(NlogN)。
貪欲法？
B_iの値から、M個のsetAを探索してB_iと同じ値の要素を削除するとTLEになります。
B_iの値とM個の配列Aのインデックスを保管するデータ構造を用意しましょう。

１、B_iの値があるM個のsetAのindexを管理するmapを用意します。
２、B_iのループし、mapからindexを管理している配列を取得します。
３、setAからB_iの値を削除します。
４、setのsizeが0ならansにインクリメントします。

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<set<int>> A(M);
    map<int, vector<int>> mp;
    rep(i, M){
        int K;
        cin >> K;
        rep(j, K){
            int a;
            cin >> a;
            A[i].insert(a);
            mp[a].push_back(i);
        }
    }

    vector<int> B(N);
    rep(i, N) cin >> B[i];

    int ans = 0;
    rep(i, N){
        vector<int> num = mp[B[i]];
        for(auto n:num){
            A[n].erase(B[i]);
            if(A[n].size() == 0) ans++;
        }
        cout << ans << endl;
    }

    return 0;
}

すぬけさんの動画にもっと綺麗なコードがあります。

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<int>> menuList(N);
    vector<int> cnt(M);
    rep(i, M){
        int k;
        cin >> k;
        cnt[i] = k;
        rep(j, k){
            int a;
            cin >> a;
            a--;
            menuList[a].push_back(i);
        }
    }

    int ans = 0;
    rep(i, N){
        int b;
        cin >> b;
        b--;
        for(auto m:menuList[b]){
            cnt[m]--;
            if(cnt[m] == 0) ans++;
        }
        cout << ans << endl;
    }

    return 0;
}

本番中にこのようなコードが書きたいです。

D - Line Crossing

O(N)
数学の問題です。
円周上に等間隔で並ぶ頂点があります。
まず交わる直線の組み合わせを求めるのでなく、全体から平行な直線の組み合わせを引きます。

円周上に等間隔で並ぶ頂点とは？

  • 正五角形の頂点ABCDEがあります
    • 直線ADと直線BCは平行ですか
      • いいえ、平行ではありません
  • 円周上にある等間隔の頂点ABCDEがあります
    • 直線ADと直線BCは平行ですか
      • はい、平行です

正多角形と円周上にある等間隔の頂点は別物です。
この照明はchat gptに質問する、または数学の参考書を読んでください。
円周上にある等間隔の頂点ABCDEを頂点1, 2, 3, 4, 5とします。
直線ADと直線BCは直線1, 4と直線2, 3です。

a_1 + b_1 = a_2 + b_2

が成り立っています。
N < a + bなら(a + b) % Nを行います。
M個の線分が交わる最大数は、

ans = M * (M - 1) / 2

これは漸化式の単元の知識になります。
検索して見て下さい。
(a+b)%Nの値が同じ線分を探索して、平行な線分の組み合わせをansから引きます。

C++
    ll ans = M * (M-1) / 2;
    for(auto c:cnt){
        ans -= c * (c-1) / 2;
    }
    cout << ans << endl;

考察が終わりました。

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() {
    ll N, M;
    cin >> N >> M;

    vector<ll> cnt(N);
    rep(i, M){
        ll a, b;
        cin >> a >> b;
        a--; b--;
        cnt[(a+b)%N]++;
    }

    ll ans = M * (M-1) / 2;
    for(auto c:cnt){
        ans -= c * (c-1) / 2;
    }
    cout << ans << endl;

    return 0;
}
1
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
1
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?