競技プログラミング練習記 No.34【ABC126練習】

初回 -> [はじめに](https://qiita.com/easychoco/items/a9ae28aca97cfe47091f)

[ABC126](https://atcoder.jp/contests/abc126)を解きました。
5完です！

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  2min |-| 7ms|
| B |  8min |-| 7ms|
| C | 28min |確率|9ms|
| D | 33min |Dijkstra法| 74ms|
| E | 11min |UnionFind木| 49ms|



## A - Changing a Character
```c++
  int n, k;
  char s[55];
  cin >> n  >> k >> s;
  s[k-1] += 'a' - 'A';
  cout << s;
```
`char`型は内部では文字コードを数値として持っています。
また、小文字同士、大文字同士は連番です。
この性質より、`A`をひいて`a`を足すと大文字を小文字に変換できます。

## B - 	YYMM or MMYY
``` c++
  int s;
  cin >> s;

  int front = s / 100;
  int back = s % 100;

  bool yymm = (front < 100) && (0 < back) && (back <= 12);
  bool mmyy = (0 < front) && (front <= 12) && (back < 100);

  if (yymm && mmyy) cout << "AMBIGUOUS";
  else if (yymm) cout << "YYMM";
  else if (mmyy) cout << "MMYY";
  else cout << "NA";
```
問題文では文字列とありますが、数値として受け取りました。
受け取った文字の前半と後半で分割する必要があり、数値のほうが分けやすかったためです。

分割した後はfizzbuzzに似ていますね。
YYMMフォーマットかMMYYフォーマットかを判定して答えです。

## C - 	Dice and Coin
``` c++
  int n, k;
  cin >> n >> k;

  double ans = max(0, n - k + 1);
  for(int i = 1; i <= min(n, k - 1); ++i)
  {
    double prob = pow( 2, (int)( -0.0000001 - ceil( log(k / (double)i) / log(2) ) ) );
    ans += prob;
  }
  printf("%.10f\n", ans / (double)n);
```
確率の問題ですね。
初めの点数が`i`の時、ダイスを振って点数を2倍ずつ増やします。
この時、`K`点以上にするには`log2 (K/i)` 回必要ですね。
整数にしたいので天井関数`ceil`を適用します。

数式にまとめると以下の式になります。

```math
\frac{1}{N} \sum_{i=1}^{N} \frac{1}{2}^{ceil(log_2 \frac{K}{i})}
```

プログラムでは、`double` -> `int` の変換で数値が変わらないように`0.0000001`を足しています。
これは浮動小数点の性質より必要なことです。[ABC169-C](https://atcoder.jp/contests/abc169/tasks/abc169_c)がこの現象を扱った問題なので名前だけ紹介しておきます。

## D - Even Relation


``` c++
using P = pair<int, int>;
const ll INF = 1LL << 60;
struct Edge{ ll cost, to; };

void solve()
{
  ll n, u, v, w;
  cin >> n;
  vector< vector<Edge> > G(n, vector<Edge>());
  for(int i = 0; i < n - 1; ++i)
  {
    cin >> u >> v >> w;
    u--; v--;
    G[u].emplace_back(Edge{w, v});
    G[v].emplace_back(Edge{w, u});
  }

  vector<ll> d(n, INF);
  d[0] = 0;
  priority_queue<P, vector<P>, greater<P>> que;
  que.push(P(0, 0));
  while (!que.empty())
  {
    P p = que.top();
    que.pop();
    ll node = p.second;
    if (d[node] < p.first) continue;
    for (const auto& edge : G[node])
    {
        if (d[edge.to] > d[node] + edge.cost)
        {
            d[edge.to] = d[node] + edge.cost;
            que.push(P(d[edge.to], edge.to));
        }
    }
  }

  for(int i = 0; i < n; ++i)
  {
    cout << (d[i] & 1) << endl;
  }
}
```
距離が偶数のものと奇数のもので頂点に色をつける問題ですね。
単一始点からの最短距離を求めて、その距離が偶数のものと奇数のものとでグループ分けすれば答えになります。
経路長は非負であり、単一始点の最短距離といえばDijkstr法です。

最短距離を求めた後は、距離の偶奇を出力して答えです。

## E - 1 or 2

```c++
class UnionFind{
public:
  vector<int> p;		// 親
  vector<int> rank;	// サイズ・各集合の根のみ有効
  UnionFind(int n){
    p.resize(n, -1);
    rank.resize(n, 1);
  }
  int root(int x){
    if(p[x] == -1)return x;
    else return p[x] = root(p[x]); // 深さを 1 にしている
  }
  void unite(int x, int y){
    x = root(x); y = root(y);
    if(x == y)return;
    if(rank[x] > rank[y]) swap(x, y); // rankの小さいものを下につける
    rank[y] += rank[x];
    p[x] = y;
  }
  //xが属すグループのサイズ
  int size(int x){ return rank[root(x)]; }
  bool same(int x, int y){ return (root(x) == root(y)); }
};

void solve()
{
	int n, m, x, y, z;
  cin >> n >> m;
  UnionFind uf(n);
  for(int i = 0; i < m; ++i)
  {
    cin >> x >> y >> z;
    x--; y--;
    uf.unite(x, y);
  }
  set<int> t;
  for(int i = 0; i < n; ++i)
  {
    t.insert(uf.root(i));
  }
  cout << t.size();
}
```
Aがひとつわかれば、Zを介してもう一つのAがわかりますね。
入力に矛盾はないので、わかったAからさらに別のAもわかります。
ただ、つながっていないAはわかりません。

つまり、つながっていないAの集合数を数える問題です。
つながっているとかつながっていないとか、に注意すると、グラフに帰着できることがわかります。
Aを頂点とみて、Zを介してわかるA同士をつなぎます。

与えられたグラフのうち、独立しているグラフの個数が答えになります。
また、「グラフの頂点を集合として見る」といえば[Union-Find木](https://www.google.com/search?ei=6I8BX5LCDriFr7wPnOOPkAs&q=union-find%E6%9C%A8)の登場です。

入力からUnion-Find木を構築した後、集合の数が答えになります。

以上です。ありがとうございました。