AtCoder ABC424 [A-C] 解法まとめ(C++)

はじめまして！

今回、初めてAtCoderに挑戦してみました。
A,Bは無事正解できましたが、30分ほどかかっていたようです。Cは解けませんでしたが、解説等を読んで何とか理解できました。
人に解説できるほどの実力はない初心者ですが、自分用に回答をまとめておこうと思います。
間違ってる点やアドバイス等あれば教えていただけると嬉しいです。

問題のリンク

A - Isosceles

問題

三角形の3辺の長さが与えられるので、二等辺三角形かどうかを調べる問題です。

考え方

二等辺三角形は、2つの辺の長さが等しいものを指します。
つまり、与えられる3つの数字のうち、どれか2つが等しければいい訳ですね。
各辺をa,b,cとすると、組み合わせは「aとb」「bとc」「cとa」の3パターンなので、これらを比較演算子でif文の条件に書きます。

解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a,b,c;
    //3辺の長さを取得
    cin >> a >> b >> c;
    if(a == b || b == c || c == a){//どれかが等しければ
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

B - Perfect

非効率ではありましたが、無事正解できました。
この問題で30分近く考えてたのはもったいなかったなと思います。

問題

（人の名前,　正解した問題）の組が数字で与えられます。
M問あるうち、すべて正解した人を、早い順に出力します。

考え方

2次元配列に正誤をすべてメモしました。
bool型の配列ansに、ans[人の名前][問題番号] = true or falseを入れる感じです。
全問正解が速かった順番に出力しないといけないため、ループごとに全問正解したかを判別しています。

少し厄介なのが出力方法で、2回目以降の出力には半角スペースが必要なので、firstClearという変数に1回目の出力かどうかをメモっています。

解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N,M,K;
    cin >> N >> M >> K;
    //要素数N,Mの配列を、初期値falseで宣言
    vector<vector<bool>> ans(N, vector<bool>(M, false));

    bool firstClear = true;
    //イベント数だけループ
    for(int i=0; i<K; i++){
        int a,b;
        cin >> a >> b;
        
        //「aさんは問bに正解した」
        //受け取る数は1スタートだが配列の添え字は0スタートなのでマイナス1する
        ans[a-1][b-1] = true;

        bool clear = true;
        //クリアしたかチェック
        for(int j=0; j<M; j++){
            //ansの値がfalseなら、clearをfaiseに。
            if(!ans[a-1][j]){
                clear = false;
                break;
            }
        }
        //クリアしてるかどうか
        if(clear){
            //1人目のクリア者かどうか
            if(firstClear){
                cout << a;
                firstClear = false;
            }else{
                cout << " " << a;
            }
        }
    }
}

別解

与えられる数字の組が同じになることはなく、余計なものが与えられることもありません。
つまり、どの問題に正解したかを考えなくとも、M回正解した時点でクリア確定でした。
これが分かっていれば2次元配列もいらないし、かなりシンプルに記述できますね。

別解の解答例

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N,M,K;
    cin >> N >> M >> K;
    vector<int> ans(N);

    bool firstClear = true;
    //イベント数だけループ
    for(int i=0; i<K; i++){
        int a,b;
        cin >> a >> b;
        //「aさんの正解数が1つ増えた」
        ans[a-1]++;

        //aさんがクリアしたかチェック
        if(ans[a-1] == M){
            if(firstClear){
                cout << a;
                firstClear = false;
            }else{
                cout << " " << a;
            }
        }
    }
}

C - New Skill Acquired

私は全く解けませんでした。
そもそも問題の意味を、与えられた順番にスキルを取得していくものだと誤解していたため、無駄に40分くらい考えていました…
とはいえ問題を理解していても有向グラフについて知らなかったので、時間内に解くのは厳しかったと思います。

問題

数字の組（a, b）が与えられます。
i番目の組が(0, 0)だった場合、スキルiは取得できています。
(0, 0)でない組(a, b)だった場合、スキルaまたはスキルbが取得できていればスキルiは取得できます。
最終的に取得できたスキルの数を出力します。

考え方

例えば、以下のような数字の組だったとします
1：(5, 3)
2：(2, 2)
3：(5, 4)
4：(0, 0)
5：(2, 2)

まずスキル1を考えると、スキル5か3の習得が必要です。

そしてスキル5にはスキル2、スキル2にはスキル2…となり、スキル5は取得できません。
一方、スキル3の方は、スキル5か4が必要で、スキル5は取れないけどスキル4は(0, 0)なので取れています。
よって、スキル3は取れることが分かり、それによってスキル1も取れます。

したがって、答えは１・３・４の3つです。

有向グラフとは

突然ですが答えを言うと、この問題は有向グラフというのもを用います。

例えば、twitter(現x)のフォローについて考えてください。
あなた（Zさん）がA,B,Cさんをフォローしてるなら、Z→A、Z→B、Z→Cのように矢印で表現します。また、D,EさんにフォローされてたらD→Z、E→Zのようになりますね。

それを複数のユーザーについてまとめて図で表すと、複雑な蜘蛛の巣みたいなものが出来上がりますよね。それが有向グラフです（たぶん）。

詳しくは以下の記事が分かりやすいと思います。私はここで初めて勉強しましたが、すごくスムーズに理解できました！

今回の問題の場合

さて、今回の問題の場合に落とし込んでいきましょう。

ダメな例：

「まずスキル1を考えると、スキル5か3の習得が必要です。」
これを有効グラフで表すと1→5と1→3ですね。これを繋げていけば…とはじめに思ったのですが、この方法だとたどるときのスタート地点がN個になり、処理回数が多くなりすぎるため微妙だなって思いました…

正しい例：

「まずスキル1を考えると、スキル5か3の習得が必要です。」
これを次のように言い換えます。
「スキル5を取ると、スキル1も取得できます。」
「スキル3を取ると、スキル1も取得できます。」
つまり5→1、3→1ですね。
この方法ならたどる時のスタート地点は(0,0)の個数になり、実装も簡単です。

さらに、以下の文も言い換えてみましょう。
「スキル4は(0,0)なので取れています。」
これは、架空のスキル「スキル0」を用意すると、
「スキル0を取ると、スキル4も取得できます。」
こうするとスタート時点はスキル0の1か所のみです。しかも取得データを配列に入れるときの場合分けが不要になるので簡単です。
ただし、スキル0は実際には存在しないので、出力時に取得スキルの数を1個マイナスしましょう。

解答例

#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v, int &count) {
    seen[v] = true;
    count++;

    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue;
        dfs(G, next_v, count);
    }
}

int main(){
    int N;
    cin >> N;
    Graph G(N+1);
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        //「スキルaを取ると、スキルiも取得できます。」
        //「スキルbを取ると、スキルiも取得できます。」
        G[a].push_back(i+1);
        G[b].push_back(i+1);
    }

    int count = 0;
    // 0をスタートとした探索
    seen.assign(N+1, false); // 全頂点を「未訪問」に初期化
    dfs(G, 0, count);

    //スキル0は存在しないので、1つ引く
    cout << count - 1 << endl;
}

探索の部分（関数dfs）については、先ほど紹介した記事からコピペさせていただきました。

今回の感想

今回は初参加ということで、B問題まで解ければいいかなと思っていたのでとりあえずは満足です。
次回はA,Bをもっと素早く解けるようにしたいです。

長期的にはアルゴリズムの勉強をしないとC問題には立ち向かえなさそうですね。
とりあえず過去問のC問題にいくつか触れてみて、出会ったアルゴリズムから覚えていこうと思います。