[AtCoder]AtCoder Beginner Contest 126

# はじめに
* AtCoder Beginner Contestの過去問の解法及び提出したソースコードをまとめています。
* 基本的に自分が振り返ることを目的としておりますが、誤りや気になった点、その他質問等もお待ちしておりますので遠慮なくお願いします。

# コンテストページ
https://atcoder.jp/contests/abc126

# A問題
ASCIIコードでアルファベットの小文字と大文字の差は32なのでK文字目に32を足します。

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

int main(){
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    s[k-1] += 32;
    cout << s << endl;
    return 0;
}
```
# B問題
入力を文字列ではなく整数で受け取り、前半二桁と後半二桁に分割します。
YYMMまたはMMYYが成り立つ条件はMM部分が1以上12以下(1月から12月)であることなので、
それぞれについて判定し、最後に条件通りに出力してあげます。

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

int main(){
    int s;
    cin >> s;
    int fh = s/100; // 前半二桁を取得
    int sh = s%100; // 後半二桁を取得
    bool yymm,mmyy;

    if(fh <= 12 && fh > 0) mmyy = true;
    else mmyy = false;

    if(sh <= 12 && sh > 0) yymm = true;
    else yymm = false;

    string ans;
    if(mmyy && yymm){
        ans = "AMBIGUOUS";
    }
    else if(mmyy){
        ans = "MMYY";
    }
    else if(yymm){
        ans = "YYMM";
    }
    else{
        ans = "NA";
    }

    cout << ans << endl;

    return 0;
}
```
# C問題
出た目iから表を出し続けk以上になる確率は1/(iに2をかけ続けkを超える回数)で割った値です。
またサイコロの各目が出る確率は1/Nです。
よって各目について成功する確率を求めて足し合わせることで答えが求まります。

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

int main(){
    int n,k;
    cin >> n >> k;
    double ans = 0;

    for(int i = 1; i <= n; i++){
        double b = 1;
        int x = i;
        while(x < k){
            x *= 2;
            b /= 2;
        }
        ans += b/n;
    }

    cout << setprecision(12) << ans << endl;

    return 0;
}
```
# D問題
無向グラフを任意の点から幅優先探索(深さ優先でもOK)で条件に従って塗り分けます。

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

struct Edge{
    int to,w;
    Edge(int to, int w):to(to), w(w){}
};

int main(){
    int n;
    cin >> n;
    vector<vector<Edge>> g(n);
    vector<int> ans(n, -1); // -1:色が未決定

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

    ans[0] = 0;
    queue<int> que;
    que.push(0);
    while(!que.empty()){
        int cur = que.front(); que.pop();

        for(auto& e : g[cur]){
            if(ans[e.to] != -1) continue;
            if(e.w % 2 == 0) ans[e.to] = ans[cur];
            else ans[e.to] = 1 >> ans[cur];
            que.push(e.to);
        }
    }

    for(int i = 0; i < n; i++){
        cout << ans[i] << endl;
    }

    return 0;
}
```
# E問題
与えられる入力に矛盾がないことからZの値は関係なく、任意の頂点の数がわかれば同じ連結成分のすべての数字がわかります。
よって答えは連結成分数が答えとなります。
連結成分数の求め方は再帰型の深さ優先探索で求めるのが鉄板です。

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

vector<vector<int>> a;
vector<int> visited;

// 一つ以上の未探索の頂点があればtrue
bool search(int x){
    if(visited[x]) return false;
    visited[x] = true;
    for(auto e : a[x]) search(e);
    return true;
}

int main()
{
    int n,m;
    cin >> n >> m;
    a.resize(n);
    visited.resize(n);

    for(int i = 0; i < m; i++){
        int x,y,z;
        cin >> x >> y >> z;
        x--;y--;
        a[x].push_back(y);
        a[y].push_back(x);
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        if(search(i)) ans++;
    }
    
    cout << ans << endl;
    return 0;
}
```

# F問題(未AC)
まだ解いておりません。