AtCoder Beginner Contest 274

## [A - Batting Average](https://atcoder.jp/contests/abc274/tasks/abc274_a)

O(1)
B<Aの為、B/Aで整数部分は１桁になる。
少数の3桁の制限を行う。

```
fixed << setprecision((n))
```

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    double a, b;
    cin >> a >> b;
    cout << fixed_setprecision(3) << b / a << endl;
    return 0;
} 
```

## [B - Line Sensor](https://atcoder.jp/contests/abc274/tasks/abc274_b)

O(HW)
グラフを作成。y軸方向の'#'をカウントする。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<char>> C(H, vector<char>(W, '.'));

    rep(i, H){
        string s;
        cin >> s;
        rep(j, W){
            C[i][j] = s[j];
        }
    }

    vector<int> res(W);
    rep(i, W){
        int sum = 0;
        rep(j, H){
            if(C[j][i] == '#') sum++;
        }
        res[i] = sum;
    }

    rep(i, W){
        cout << res[i];
        if(i < W-1) cout << ' ';
    }
    cout << endl;

    return 0;
} 
```

## [C - Ameba](https://atcoder.jp/contests/abc274/tasks/abc274_c)

O(N)
1~(2N+1)までのアメーバがいます。
「番号Aiのアメーバが分裂して消滅し、新たに 2 匹のアメーバが生まれ、それらにそれぞれ 2i,2i+1 と番号をつけた」
iとアメーバの番号は、対応していますが別の数字と考えましょう。

```
4
1 3 5 2
```

の入力として、i=1の1番のアメーバの分裂数は0。

```
1 2 3 4 5 6 7 8 9
0 ? ? ? ? ? ? ? ?
```

i=1のアメーバは2*iと2i+1の番号のアメーバに分裂します。
1番のアメーバの分裂数＋１を代入します。

```
1 2 3 4 5 6 7 8 9
0 1 1 ? ? ? ? ? ?
```

i=2の3番のアメーバは4, 5番のアメーバに分裂します。
３番のアメーバの分裂数＋１を代入します。

```
1 2 3 4 5 6 7 8 9
0 1 1 2 2 ? ? ? ?
```

i=3の5番アメーバは6, 7番のアメーバに分裂します。
5番のアメーバの分裂数＋１を代入します。

```
1 2 3 4 5 6 7 8 9
0 1 1 2 2 3 3 ? ?
```

i=4の2番のアメーバは8, 9番のアメーバに分裂します。
2番のアメーバの分裂数＋１を代入します。

```
1 2 3 4 5 6 7 8 9
0 1 1 2 2 3 3 2 2
```

配列amebasに、アメーバの番号をkeyとして、分裂数を代入します。

```
amebas[2*i] = amebas[親の番号] + 1;
amebas[2*i+1] = amebas[親の番号] + 1;
```

計算式ができました。
1≤Ai≤2i−1, の制約がある為、Aの配列をソートする必要はなさそうです。
コーディングをします。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N;
    cin >> N;
    vector<P> A;
    rep(i, N){
        int a;
        cin >> a;
        A.push_back(P(i+1, a));
    }
    ll max_ameba = 2*N + 1;
    vector<ll> amebas(max_ameba+1, -1);
    amebas[1] = 0;
    for(ll i=1; i<=N; i++){
        int index = A[i-1].first;
        int parent = A[i-1].second;
        if(amebas[2*index] == -1) amebas[2*index] = amebas[parent] + 1;
        if(amebas[2*index+1] == -1) amebas[2*index+1] = amebas[parent] + 1;
    }

    for(ll i=1; i<=max_ameba; i++){
        cout << amebas[i] << endl;
    }

    return 0;
} 
```