AtCoder Beginner Contest 204 備忘録

当日未参加
A：AC
B：AC
C：回答見ながら
D：
E：
F：

A - Rock-paper-scissors
https://atcoder.jp/contests/abc204/tasks/abc204_a
じゃんけんであいこになる手を出力させるやつ。
当然ながら全部同じの時と全部違うときの2通り。
全部違うときは全部足したら3になるようにすればよい。

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

int main(void){
    int x,y,z;
    cin>>x>>y;
    if(x==y){
        z=x;
    }
    else{
        z=3-x-y;
    }
    cout<<z<<endl;
}

B - Nuts
https://atcoder.jp/contests/abc204/tasks/abc204_b
10以上の時は10個残して木の実をとる、というのをそのまま実装するだけ。

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

int main(void){
    int N;
    int A[1100];
    cin>>N;
    long long ans=0;
    for(int i=0;i<N;i++){
        cin>>A[i];
        if(A[i]>10){
            ans=ans+A[i]-10;
        }
    }
    cout<<ans<<endl;
}

C - Tour
https://atcoder.jp/contests/abc204/tasks/abc204_c
動的計画法の幅優先探索を用いる問題。

[グラフ入力]
・動的配列 vector<vector<int>>で、各点から訪問できるところを入力する。

[探索]
・探索待ち配列（q:queue配列）と訪問済み配列(vis：set配列)を用意する。
・ある点をスタート地点として選ぶ
・スタート地点を探索待ち、訪問済み配列に入力する。
・探索待ち配列から探索待ちの値を取り出す。
・探索待ち配列から取り出した値を消す。
　　※最初に入力した値を取出し、消去するのがが幅優先探索、
最後に入力した値を取り出すのが深さ優先探索
・探索待ちから取り出した値から、訪問できるところを先の動的配列から取り出す。
・取り出した訪問できるところが、訪問済みかどうかを判定
・未訪問の場合は、探索待ちに追加、訪問済みに追加する
・探索待ちに追加されたものがある場合は、Whileで探索待ちがなくなるまで繰り返す
※訪問できるところがなくなったら探索待ちに追加されなくなるので終了する。
・いくつ訪問できたかを出力し、ansに加算する。
・次の地点をスタート地点にして、再度上記探索を繰り返す。

この流れがいわゆる幅優先探索。
これは知識として知らないとまず実装できない類。
とにかく数こなして慣れていくしかないタイプのやつ。

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

int main(){
	int N,M;
	cin >> N >> M;
    vector<vector<int>>G(3000);//グラフ用

	for(int i=0;i<M;i++){//グラフ入力
		int a,b;
		cin >> a >> b;  
		G[a].push_back(b);
	}
    int ans=0;
    for(int i=1;i<=N;i++){//スタート地点を全探索
        queue<int>q;//探索待ち用
        set<int>vis;//訪問した記録用
        q.push(i);//まずスタート地点をキューに入れる
        vis.insert(i);//スタート地点を訪問済みに入れる

    while(q.empty()==0){//探索待ちになんかある限りループ
        int A =q.front();//探索待ちの先頭を取り出す
        q.pop();//キューの先頭を消す
        for(auto j:G[A]){//Aからいけるところを全出力する
            if(vis.count(j)==0){//未訪問の場合だけ。
                q.push(j);//探索待ちに追加
                vis.insert(j);//訪問済みに追加
            }
            //未訪問あったらqが加算されるので、whileﾙｰﾌﾟ継続
            //訪問済みの場合はqが加算されないので、qが空になってループ解除
        }
    }
        ans=ans+vis.size();//i地点からいける数をansに足す
    }
	cout << ans<<endl;;
}