AtCoder 生活　68日目

[前回](https://qiita.com/flandrescarlet237/items/8de291bff58c6f12bcd4)

#68日目
今回は茶色diffの問題を2問解き、とバーチャル参加を2回しました。

|問題|難易度|自力で解けた|かかった時間|
|:-:|:-:|:-:|---|---|
|ABC168|D|✕|147分20秒|
|ABC167|C|✕|70分20秒|

![スクリーンショット 2020-05-28 11.45.23.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606053/69de28f0-a136-1206-b794-79ce5c21c752.png)
![スクリーンショット 2020-05-28 13.46.30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/606053/0536138a-6770-85a1-54c1-cc3621fc64a6.png)


##[ABC145](https://atcoder.jp/contests/abc145)

###A

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int main(){
    int r;
    cin >> r;
    cout << r*r << endl;
}

```

###B


```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pil = pair<pii,int>;


int main(){
    int n;
    string s;
    cin >> n >> s;
  	if(n%2 != 0){
      	cout << "No" << endl;
    }
  	else{
        string a = s.substr(0,n/2);
        string b = s.substr(n/2,n/2);
        if(a == b)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

```

###C

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int d(int a){
    return a*a;
}

int s (int a){
    int n = 1;
    while(a > 1){
        n *= a;
        a--;
    }
  	return n;
}

int main(){
    int n;
    cin >> n;
    vector<pii> x(n);
    rep(i,n){
        int a,b;
        cin >> a >> b;
        x[i].first = a;
        x[i].second = b;
    }
    double ans = 0;
    rep(i,n){
        rep(j,n){
            int t = d(x[i].first - x[j].first) + d(x[i].second - x[j].second);
            ans += pow(t,0.5);
        }
    }
    int t = s(n);
    cout << fixed << setprecision(10) << ans*(t/n)/t << endl;
}

```


##[ABC144](https://atcoder.jp/contests/abc144)

###A

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int main(){
    int a,b;
    cin >> a >> b;
    if(9 < a || 9 < b) cout << -1 << endl;
    else cout << a*b << endl;
}

```

###B


```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pil = pair<pii,int>;


int main(){
    int n;
    cin >> n;
    bool ok = false;
    for(int i = 1;i < 10;i++){
        for(int j = 1;j < 10;j++) if(i*j == n)ok = true;
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}

```


##[ABC168_D](https://atcoder.jp/contests/abc168/tasks/abc168_d)

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;
vector<int> to[100005];

int main(){
    int n,m;
    cin >> n >> m;
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--;b--;
        to[a].push_back(b);
        to[b].push_back(a);
    }

    queue<int> q;
    vector<int> dist(n,INF);
    vector<int> pre(n,-1);
    dist[0] = 0;
    q.push(0);
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int u : to[v]){
            if (dist[u] != INF) continue;
            dist[u] = dist[v]+1;
            pre[u] = v;
            q.push(u);
        }
    }
    cout << "Yes" << endl;
    rep(i,n){
        if(i == 0) continue;
        int ans = pre[i];
        ans++;
        cout << ans << endl;
    }
}

```

解くのにかかった時間：147分20秒
感想：BFSに慣れない


##[ABC167_C](https://atcoder.jp/contests/abc167/tasks/abc167_c)

```c++

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    int n,m,x;
    cin >> n >> m >> x;
    vector<int> c(n);
    vector<vector<int>> a(n,vector<int>(m));
    rep(i,n){
        cin >> c[i];
        rep(j,m) cin >> a[i][j];
    }
    int ans = INF;
    rep(s,1<<n){
        int cost = 0;
        vector<int> d(m);
        rep(i,n){
            if(s >> i & 1){
                cost += c[i];
                rep(j,m) d[j] += a[i][j];
            }
        }
        bool ok = true;
        rep(j,m) if(d[j] < x) ok = false;
        if(ok) ans = min(ans,cost);
    }
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
}

```

解くのにかかった時間：70分20秒
感想：bit全探索であることに気付けるようにはなったが、解けなかった


###最後に
どのアルゴリズムを使えばいいのかはわかるようになったが、アルゴリズムを使いこなせない