AtCoder Beginner Contest 126

C - Dice and Coin

https://atcoder.jp/contests/abc126/tasks/abc126_c

方針

サイコロの目が かつ、すぬけ君が勝つ確率を とします。各 を求めてから総和を取る方針でいきます。

コインは、得点が 以上になるまで連続で表を引き続けなければいけません。いま ですので、実際に得点を2倍にしていきながら、何回連続で表を引けば を越えるかを調べることができます。
この回数を とすると、サイコロの目が となる確率が 、その後 回連続でコインが表になる確率が ですから、
　　
となります。

ソースコード

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

int main(){
    int N, K;
    cin >> N >> K;

    double ans = 0.0;
    for(int n=1; n<=N; n++){
        int k = 0; // コインの表を出さなければいけない回数
        int point = n; // 現在の得点

        // k を求める。
        // point が K 以上になるまで、得点を2倍にしつつ k を増やす。
        while(point < K){
            k++;
            point *= 2;
        }

        ans += 1.0/N/pow(2,k);
    }    
    cout << setprecision(12) << ans << endl;
}

D - Even Relation

https://atcoder.jp/contests/abc126/tasks/abc126_d

方針

下図のように、奇数長の辺を跨ぐときに色が反転するように色を決めれば良いです。ここで黒い辺は偶数長、赤い辺は奇数長です。偶数長の辺のみで結ばれた部分木内の任意の2頂点間は、全て偶数長の辺のみを通って行き来できるため、問題文の条件を満たします。また奇数長の辺を通って同色の頂点へ行く場合も、奇数長の辺を必ず偶数回だけ通ることになるため、やはり問題文の条件を満たします。

実装の際は、根は適当に決めてよいので頂点 1 を根とします。また根の色は好きに決めてよいので、ここでは白としておきます。あとは葉に向かって深さ優先探索しながら、

• 親と子が偶数長の辺で結ばれる時、親子の色は同じ
• 親と子が奇数長の辺で結ばれる時、親子の色は異なる

という条件に従いながら子の色を付けていけば答えが得られます。

ソースコード

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

struct edge{
    // 辺を表す。
    //     to  : 宛先
    //     cost : 長さ
    int to, cost;
};

vector<vector<edge>> tree;
vector<int> color;

void dfs(int u, int p){
    // u : 今見ている頂点
    // p : u の直前にいた頂点、すなわち u の親。
    int n = tree[u].size();
    for(int i=0; i<n; i++){
        int v = tree[u][i].to; // u の次に行く頂点
        int w = tree[u][i].cost;

        // 根から葉へ探索するので、v==pの場合はスキップ
        if(v==p) continue;

        if(w%2==0){
            // 偶数長の辺で結ばれる親と子は同じ色。
            color[v] = color[u];
        }else{
            // 奇数長の辺で結ばれる親と子は異なる色
            color[v] = 1 - color[u];
        }

        // u から v へ移動する
        dfs(v, u);
    }
}

int main(){
    int N;
    cin >> N;

    // tree[u][i] は 辺 u から伸びる i 番目の辺を表す。
    tree = vector<vector<edge>>(N+1, vector<edge>());
    for(int i=0; i<N-1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edge e;  e.to = v;  e.cost = w;
        tree[u].push_back(e);
        e.to = u;
        tree[v].push_back(e);
    }

    int root = 1;  // 頂点 1 を根とする。
    color = vector<int>(N+1, 0);  // 各頂点の色を格納。
    color[root] = 0; // 根の色は白にする。
    dfs(root, 0); // 根から深さ優先探索する。
    for(int i=1; i<=N; i++){
        cout << color[i] << endl;
    }
}

E - 1 or 2

https://atcoder.jp/contests/abc126/tasks/abc126_e

方針

情報「 が偶数」 が与えられたとします。このとき、 の偶奇にかかわらず、 のどちらかの値が分かれば、もう一方の値も分かります。
つぎに、情報「 が偶数」 が与えられたとしましょう。最初の情報も利用すると、 のどれか 1 つの値が分かれば、残りの値も全てわかります。

以上のことから、次のように考えるとよいです：

1. 個の頂点 1, 2, ……, を用意する。
2. 各 i で頂点 と 頂点 の間を辺で結ぶ
3. 最終的に得られたグラフの、連結成分の数が答え。

この実装は Union-Find木 を使うと楽にできます。各連結成分ごとに根が 1 つずつあるので、根の数を数える問題に帰着しますが、頂点 i が根であるか否かは、 であるか否かで判定できます。

ソースコード

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

// Union-Find木
struct union_find{
    union_find(int n){
        par = vector<int>(n, -1);
    }
    int find(int x){
        if(par[x] < 0) return x;
        else return par[x] = find(par[x]);
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(par[x] < par[y]) swap(x,y);
        par[x] += par[y];
        par[y] = x;
    }
    int getSize(int x){
        return -par[x];
    }

    private:
        vector<int> par;
};


int main(){
    int N, M;  cin >> N >> M;
    union_find uf(N);
    for(int i=0; i<M; i++){
        int X, Y, Z;
        cin >> X >> Y >> Z;

        // union-find木の頂点を 0~N-1 としているので、1 ずつ引いておく
        X--;  Y--;
        uf.unite(X, Y);  // X と Y を結合する
    }

    int ans = 0;
    // union-find木の根の数を数える。
    for(int i=0; i<N; i++){
        if(uf.find(i) == i) ans++;
    }

    cout << ans << endl;
}