AtCoder Beginner Contest 226

##[A - Round decimals](https://atcoder.jp/contests/abc226/tasks/abc226_a)

O(1)
round関数を使用すると四捨五入できます。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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;
    cin >> a;
 
    cout << round(a) << endl;
 
    return 0;
}
```

##[B - Counting Arrays](https://atcoder.jp/contests/abc226/tasks/abc226_b)

O(N)
数列の種類をカウントする問題です。
C++にはsetがあります。
vector使うとうまくいきますね。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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 N;
    cin >> N;
 
    set<vector<int>> st;
    rep(i, N){
        int L;
        cin >> L;
 
        vector<int> a(L);
        rep(j, L) cin >> a[j];
        st.insert(a);
    }
    cout << st.size() << endl;
 
    return 0;
}
```

##[C - Martial artist](https://atcoder.jp/contests/abc226/tasks/abc226_c)

O(不明)
問題文を読むとDFSかBFSの問題と感じました。
しかし、単純に考えてN^2の全探索では通らないと考えました。
実際に提出してTLEが３つ存在しました。

そこで一度探索した経路を記録し、枝刈りすることで間に合うのではないかと考えました。
N番目の要素が必要な技を先頭から計測して行きました。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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; }
 
vector<int> T;
vector<vector<int>> A;
vector<int> F;
ll res=0;
 
void dfs(int cnt){
    if(F[cnt]==0){
        F[cnt]=1;
        res += T[cnt];
    }
 
    if(A[cnt].size() == 0){
        return;
    }
 
    rep(i, A[cnt].size()){
        int a = A[cnt][i]-1;
        if(F[a] == 1) continue;
        dfs(A[cnt][i]-1);
    }
}
 
int main() {
    int N;
    cin >> N;
 
    T.resize(N);
    A.resize(N);
    F.resize(N);
    rep(i, N){
        int K;
        cin >> T[i] >> K;
        A[i].resize(K);
        rep(j, K) cin >> A[i][j];
    }
    dfs(N-1);
    cout << res << endl;
 
    return 0;
}
```

##[D - Teleportation](https://atcoder.jp/contests/abc226/tasks/abc226_d)

O(N^2)
N<=500の為、全探索ができます。

２点間の距離を計測。
x軸, y軸の距離も０以上ならgcdを使用し、最小のx, yの組み合わせを計測します。
双方向なので符号を逆にした距離も計測します。
片方の距離が0の場合、もう片方は１にします。
種類なのでsetを使用します。

```C++:C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; 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 gcd(int a, int b){
  if(a%b == 0){
    return b;
  }else{
    return gcd(b, a%b);
  }
}
 
int main() {
    int N;
    cin >> N;
 
    vector<int> x(N);
    vector<int> y(N);
    set<P> st;
    rep(i, N) cin >> x[i] >> y[i];
 
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            int xx = x[j] - x[i];
            int yy = y[j] - y[i];
            if(xx!=0 && yy!=0){
              int t = gcd(xx, yy);
              xx = xx/t;
              yy = yy/t;
            }else{
              if(xx != 0) xx = 1;
              if(yy != 0) yy = 1;
            }
            
            st.insert(P(xx, yy));
            st.insert(P(-xx, -yy));
        }
    }
 
    cout << st.size() << endl;
 
    return 0;
}
```