ABC292 参加記録

ABC292に参加しました。A~Dの解法(?)と感想をゆるゆる書いていきます。
コンテストのリンク:

• https://atcoder.jp/contests/abc292

A - CAPS LOCK

問題概要

英小文字のみからなる文字列 $S$ が与えられます。
$S$ の各文字を大文字に変換して、出力してください。

• $1\leq |S|\leq100$

問題リンク:

• https://atcoder.jp/contests/abc292/tasks/abc292_a

解法

C++にはtoupperがあるので、それを使うといいかなぁと。ASCIIコードでやってもいいとは思う。

実装例

toupperを使う

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++){
        s[i] = toupper(s[i]);
    }
    cout << s << '\n';
}

• AC:6ms

ASCIIコードをつかう

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++){
        int id = s[i] - 'a';    //何番目のアルファベットか?
        s[i] = 'A' + id;
    }
    cout << s << '\n';
}

• AC:5ms

B - Yellow and Red Card

問題概要

$N$ 人のサッカー選手がいます。
サッカーでは、以下の条件のうち少なくとも一方が満たした選手は退場処分を受けます。

• イエローカードを累計 $2$ 枚提示される
• レッドカードを提示される

以下のクエリが $Q$ 個与えられるので順に処理してください。

1. 1 x:選手 $x$ にイエローカードを提示する
2. 2 x:選手 $x$ にレッドカードを提示する
3. 3 x:選手 $x$ が退場処分を受けたかどうか(Yes/No)を出力

なお、退場処分を受けた選手には以後カードを提示することはありません。

• $1\leq Q\leq 100$
• $1\leq N\leq 100$
• 入力はすべて整数

問題リンク:

• https://atcoder.jp/contests/abc292/tasks/abc292_b

解法

• cnt[x]:選手 $x$ の食らったイエローカードの個数
• check[x]:選手 $x$ が退場処分を食らったか?

を作っておく。これを丁寧に管理していけばいい。

実装例

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n, q;
    cin >> n >> q;

    vector<int> cnt(n);
    vector<bool> check(n,false);

    for (int t = 0; t < q; t++){
        int type;
        cin >> type;
        if (type == 1){
            int x;
            cin >> x;
            x--;
            cnt[x]++;

            if (cnt[x] >= 2){
                check[x] = true;
            }
        }
        else if (type == 2){
            int x;
            cin>>x;
            x--;
            check[x] = true;
        }
        else{
            int x;
            cin >> x;
            x--;
            if (check[x]){
                cout << "Yes\n";
            }
            else{
                cout << "No\n";
            }
        }
    }
}

• AC:4ms

C - Four Variables

問題概要

正整数 $N$ が与えられる。
正整数の組 $(A,B,C,D)$ であって、

$$AB+CD=N$$

なるもの個数を求めよ。

• $1\leq N\leq2\times10^5$
• 入力はすべて整数

問題リンク:

• https://atcoder.jp/contests/abc292/tasks/abc292_c

解法

方針

$AB,CD$ を一つと見て

$$S_1=AB,S_2=CD$$

と置けば、条件が

$$S_1+S_2=N$$

となり、答えは、

全ての $S_1+S_2=N$ なる $(S_1,S_2)$ に対する

「 $S_1$ に対応する $(A,B)$ の個数」と「 $S_2$ に対応する $(C,D)$ の個数」の積

の和

である。

• $S_1$ に対応する $(A,B)$ の個数は $AB=S_1$ なる $(A,B)$ の個数
• $S_2$ に対応する $(C,D)$ の個数は $CD=S_2$ なる $(C,D)$ の個数

なので、

• $v[x]=$ 正整数の組 $(a,b)$ であって、 $ab=x$ なるものの個数

というのが知りたくなってくる(なりますよね?)
これを列挙することができれば

• $S_1$ に対応する $(A,B)$ の個数は $v[S_1]$
• $S_2$ に対応する $(C,D)$ の個数は $v[S_2]$

なので、答えが

$$\sum_{S_1+S_2=N かつ 0<S_1,S_2}{v[S_1] v[S_2]}$$

すなわち

$$\sum_{1\leq S_1 <N}{v[S_1] v[N-S_1]}$$

となります。したがって、 $v$ を列挙しておけばこの計算は $O(N)$ でできます。

$v$ の列挙には

• $O(N\sqrt N)$
• $O(N\log N)$

のふたつ...があると思う。

$O(N\sqrt N)$

各 $x$ について、 $x=ab$ より $(a,b)$ は約数列挙の要領で $O(\sqrt x)$ で数えることができる。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


int calc_v(int n){
    int ans = 0;
    //aは√nまで調べれば十分
    for (int a = 1; a * a <= n; a++){
        if (n % a != 0){
            continue;
        }

        if (a * a == n){
            ans++;
        }else{
            //a!=bのときは(a,b)に加えて、(b,a)も条件を満たす
            ans += 2;
        }
    }

    return ans;
}
int main(){
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++){
        v[i] = calc_v(i);
    }
}

$O(N\log N)$ 解法

次のようなコードで $v[x]$ を列挙できます。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int a = 1; a <= n; a++){
        for (int b = 1; a * b <= n; b++){
            v[a * b]++;
        }
    }
}

一見 $O(N^2)$ ですが...じつは調和級数による計算量解析から、 $O(N\log N)$ で収まることがわかります。
各 $a$ について、 $b$ は最大でも $\lfloor\frac{N}{a}\rfloor$ なので、計算量は

$$\sum_{a=1}^{N}{\left\lfloor\frac{N}{a}\right\rfloor}\leq \sum_{a=1}^{N}{\frac{N}{a}}=N\sum_{a=1}^{N}{\frac{1}{a}}\sim N\log N$$

となることが分かります。途中、

$$\sum_{a=1}^{N}{\frac{1}{a}}\sim\log N$$

としましたが、これは不等式

$$\log N\leq\sum_{a=1}^{N}{\frac{1}{a}}\leq \log{N}+1$$

から分かります。

• https://qiita.com/ageprocpp/items/f6661deaa09dda124132

まとめ

1. $v[x]$ をどうにかして列挙する
2. $1\leq S_1 <N$ なるすべての $S_1$ について、$v[S_1] v[N-S_1]$ の合計を求める

実装例

$O(N\sqrt N)$

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++){
        for (int a = 1; a * a <= i; a++){
            if (i % a != 0){
                continue;
            }

            if (a * a == i){
                v[i]++;
            }
            else{
                v[i] += 2;
            }
        }
    }
    long long ans = 0;
    for (int s1 = 1; s1 < n; s1++){
        ans += (long long)v[s1] * v[n - s1];
    }
    cout << ans << '\n';
}

• AC:172ms

$O(N\log N)$

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int a = 1; a <= n; a++){
        for (int b = 1; a * b <= n; b++){
            v[a * b]++;
        }
    }
    long long ans = 0;
    for (int s1 = 1; s1 < n; s1++){
        ans += (long long)v[s1] * v[n - s1];
    }
    cout << ans << '\n';
}

• AC:11ms

D - Unicyclic Components

問題概要

$N$ 頂点 $M$ 辺の無向グラフが与えられる。
全ての連結成分が、以下の条件を満たすかどうか判定してください。

• 連結成分に含まれる辺の本数と、頂点の個数は等しい

• $1\leq N\leq 2\times10^5$
• $0\leq M\leq 2\times10^5$
• 入力はすべて整数

問題リンク:

• https://atcoder.jp/contests/abc292/tasks/abc292_d

解法

方針

まず、グラフ問題であること,D問題であることから、方針は主に以下の二つだとおもう。

• BFS,DFS
• UnionFind

どちらでもできそう。
今回は...正直どちらでもいいとおもう。ただ、連結成分という言葉から、UnionFindを使うほうが楽かもしれない...

BFS,DFS

本番は僕もこちらで通した。特に言うことはない...実装をみてほしい。

UnionFind

かしこいね...
各連結成分の代表元 $r$ に対して、

• edge[r]:$r$ の連結成分に含まれる辺の本数
• node[r]:$r$ の連結成分に含まれる頂点の個数

というのを持たせることで、容易に判定することができる。こちらも実装を参照してほしい

実装例

BFS(DFS)

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

//辺を表す型を作る
struct edge{
    int to;
    int idx;    //辺の番号

    edge(int to, int idx) : to(to), idx(idx){}
};

int main(){
    int n, m;
    cin >> n >> m;

    vector<vector<edge>> g(n);
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }

    vector<bool> visited(n, false), used(m, false);

    for (int s = 0; s < n; s++){
        //すでに s の連結成分が探索されていたら無視して良い
        if (visited[s]){
            continue;
        }

        //BFS
        visited[s] = true;
        queue<int> q;
        q.emplace(s);

        int node = 0, edge = 0;
        while (q.size()){
            int v = q.front();
            node++;
            q.pop();

            for (const auto &[nv, ni] : g[v]){
                if(!visited[nv]){
                    visited[nv] = true;
                    q.emplace(nv);
                }
                if(!used[ni]){
                    used[ni] = true;
                    edge++;
                }
            }
        }

        if (node != edge){
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
}

• AC:161ms

UnionFind

#include<iostream>
#include<vector>
#include<atcoder/all>
using namespace std;
using namespace atcoder;


int main(){
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> e;   //辺を管理する
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        u--, v--;
        e.emplace_back(u, v);
    }

    dsu uf(n);  //union find
    for(const auto&[u,v]:e){
        uf.merge(u, v); //繋ぐ
    }


    vector<int> edge(n), node(n);

    for (const auto &[u, v] : e){
        edge[uf.leader(u)]++;
    }

    for (int v = 0; v < n; v++){
        node[uf.leader(v)]++;
    }

    for (int r = 0; r < n; r++){
        //rが代表元じゃなかったら関係ない
        if (uf.leader(r) != r){
            continue;
        }

        if (edge[r] != node[r]){
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
}

• AC:100ms