【abc-177】個人的ふりかえり(A〜Dまで)

#ふりかえり
　ABCの３完。Aで二回WAを出したのと、Cに時間がかかりすぎたのが良くなかった。Dはやるべきことは分かったが、実装する能力がなかった。EFは見てない。

#A問題

　割り算を行う際の場合分けの境界を考えるのが未だに苦手で、結局割り切れる場合と割り切れない場合を別々に考えることにした。以下自分の提出。

```php
int main(){
  int d,t,s;
  cin >> d >> t >> s;
  
  if(d%s==0){    
    if(d/s>t){
      cout << "No" << endl;  
    }
    else{
      cout << "Yes" << endl;  
    }    
  }
  else{
    if(d/s>=t){
      cout << "No" << endl;  
    }
    else{
      cout << "Yes" << endl;  
    }
  }    
}

```
　しかし冷静に考えてみると、d、t、sを小数（double）として受ければ、場合分けは2つですむじゃん。

```php
int main(){
  double d,t,s;
  cin >> d >> t >> s;
  
  if(d/s<=t) cout << "Yes" << endl;
  else cout << "No" << endl;
}
```
　もっと冷静になると、t*sとdの大小の比較でよかったと気づいた。こういう柔軟さを身につけたい。

#B問題
　Bは特に困らなかった。まずTの一文字目をSの何文字目に対応させるかを決め、その時S（の一部）とTが何文字異なっているかを数えればいい。答えはその最小値。

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

#define rep(i, n) for (int i = 0; i<n; i++)

int main(){
  string s,t;
  cin >> s >> t;
  int n = s.size()-t.size()+1;
  int T = t.size();
  int S = s.size();
  
  int ans = 10001;
  rep(i, n){
    int sum = 0;
    rep(j, T){
      if(s[i+j]!=t[j]){
        sum++;
      }
    }
    ans = min(ans, sum);
  }
  cout << ans << endl;    
}

```

#C問題
　TLEを連発しまくって泣きそうだった。最初に考えたのは、
①積を全て求めて足す（無理に決まってるけどとりあえずやってみた）
②(積の和)={(A1+A2+...+An)の２乗-(A1*A1＋A2*A2+...+An*An)}/2 を使う
の2つ。①はもちろんTLEで、②は　/2　のせいでmodを考えるのが難しくて断念。

　最終的には、A2からAnまでの和をsumとして、A1*sum、A2*(sum-A2)、…としていけば計算量が大幅に減ることに気づいた。後は実装するのみ。

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

int main(){
  const long long C = 1000000007;
  int N;
  cin >> N;
  vector<int> V(N);
  long long sum = 0;
  for(int i= 0; i<N; i++){
    int A;
    cin >> A;
    V[i] = A;
    sum += A;
  }
  
  sum -= V[0];
  
  long long sum_mod;
  for(int i= 0; i<N; i++){
    long long X;
    X = V[i]*(sum%C);
    X %= C;
    sum_mod += X;
    sum -= V[i+1];
  }
  
  cout << sum_mod%C << endl;    
}
```
　mod(1000000007)を行う場所によって計算結果が大きく変わってしまうので注意したい（そのせいで何度もやり直した）。ある数の集合の和のmodを求めるときは、その要素のmodをとるか、最後にmodをとるようにすればいいのかな。

#D問題

　同じグループの中に友達がいない状況を作るのに必要なグループの数の最小値を求める問題。結局求めるのは「友達が最も多い集団（グループではない）の構成人数」であることは分かった。例えば友達8人の集団と友達5人の集団があるとすれば、グループを8個作れば条件は満たせるからである。
　無向グラフとして友達関係を受け取り、探索を行って頂点の数を調べればいいんじゃないかな…と思ったが、DFSもBFSもちゃんと理解していないので解けなかった。これを期にBFS（幅優先探索）勉強してみた。以下BFSを用いた方法。

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

int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> V(N+1, vector<int>(0));
  
  for(int i = 0; i<M; i++){
    int A, B;
    cin >> A >> B;
    V[A].push_back(B);
    V[B].push_back(A);
  }
  
  //BFSの準備
  vector<bool> visited(N+1, false);
  queue<int> que;
  
  int ans = 0;
  
  for(int i = 1; i<N+1; i++){
    //頂点iが訪問済みじゃないとき
    if(!visited[i]){
 
      int sum = 1;//頂点の数
      
      visited[i] = true;
      que.push(i);
      
      //BFS
      while(!que.empty()){
        int v = que.front();
        que.pop();
        
        for(int nv : V[v]){
          if(visited[nv]) continue;          
          sum++;
          visited[nv] = true;
          que.push(nv);
        }
      }
      
      ans = max(ans, sum);
    }
  }
  
  cout << ans << endl;       
}
```
　公式の解答例見てみたら、UnionFindっていうデータ構造を使っているらしいけど、そっちは時間があるときに勉強することにする。

　EFはもう少し成長してからやろうかな。