【abc-176】個人的ふりかえり（A〜E）

#ふりかえり
　A B Cの３完。Dは飛ばした。EはできそうでTLE。Fは見てない。４完への道は長い…
#A問題
　NがXで割り切れるときはN/X回、割り切れないときは(N/X+1)回焼くことになるので、その二つで場合分けした。

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

int main(){
  int N,X,T;
  cin >> N >> X >> T;
  
  int ans;
  if(N%X ==0){
    ans = (N/X)*T;
  }
  else{
    ans = (N/X+1)*T;
  }
  
  cout << ans << endl;     
}
```
#B問題
　全ての桁の総和が９の倍数かどうか判定する問題。Nの値が大きく、intやlongなどでは受け取ることができないので、とりあえずstringとして受け取り、一文字ずつintに変換して足していった。char型からint型に変換する方法がこれしか思いつかなかったけど、解けたからまあいいか。

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

int main(){
  string s;
  cin >> s;
  
  int sum = 0;
  rep(i, s.size()){
    int n;
    //char型をint型に変換
    if(s[i]=='0') n = 0;
    if(s[i]=='1') n = 1;
    if(s[i]=='2') n = 2;
    if(s[i]=='3') n = 3;
    if(s[i]=='4') n = 4;
    if(s[i]=='5') n = 5;
    if(s[i]=='6') n = 6;
    if(s[i]=='7') n = 7;
    if(s[i]=='8') n = 8;
    if(s[i]=='9') n = 9;
    sum += n;
  }

  //９の倍数か判定
  if(sum%9==0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
```

#C問題
　踏み台の高さの合計を求める問題。
　例えば自分の身長がa2、自分の前の人の身長がa1とする。もし自分の方が身長が低かったら、踏み台の高さはa1-a2で与えられる。一方自分の身長の方が高かったら、踏み台は必要ないので高さは０。したがって踏み台の高さは__max(a1-a2, 0)__で与えられる。
  したがって先頭から順にa1とa2を更新しながら、max(a1-a2, 0)の和を求めればよい。

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

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

int main(){
  int N;
  cin >> N;
  long long sum = 0;
  
  int a1;
  cin >> a1;
  
  rep(i, N-1){
    int a2;
    cin >> a2;
    sum += max(0, a1-a2);
    a1 = a2+max(0, a1-a2);
  }
  
  cout << sum << endl;
}
```
      

#D問題
　見た瞬間無理だと思って諦めた。コンテスト終了後に解説見ながらコード書いてみたけど、それでも苦労した。
　まず、そのマスにワープ何回で辿り着けるか記録する二次元配列を用意する。初期値は-2にしておいた。次に道のマスを−１に書き換える。したがってこの時点で-1は道、-2は壁を表す。


```php
  int H, W, Sx, Sy, Gx, Gy;
  cin >> H >> W >> Sx >> Sy >> Gx >> Gy;
  vector<vector<int>> num(1010,vector<int>(1010, -2));//そのマスにワープ何回で辿り着けるか記録する

  //道を入力  
  char s;
  rep(i,H){
    rep(j,W){
      cin >> s;
      if(s == '.'){
        num[i+1][j+1] = -1;
      }
    }
  }
```

　方針は、
　①BFS（幅優先探索）でスタートからワープ０回で行ける場所を列挙する
　②ワープ０回で行ける場所からワープすることで行ける場所を列挙する
　③BFSでワープ１回で行ける場所を列挙する
　④ワープ１回で行ける場所からワープすることで行ける場所を列挙する
　　（以下繰り返す）
　となる。したがって①と②の部分が書ければ、後はその繰り返しとなる。
　
　まず①から。queueを２つ使う。queはBFSのために使い、que0はワープ０回（下のコードでは、後にループさせるためp回としている）で行ける場所を貯めておくために使う。queとque0にスタート地点を挿入し、スタート地点のnumは０にする（スタート地点はもちろんワープ０回で行ける）

```php

  queue<pair<int,int>> que0;  
  queue<pair<int,int>> que;
  
  que.push(make_pair(Sx,Sy));
  que0.push(make_pair(Sx,Sy));
  num[Sx][Sy] = 0;
```

　そしてBFSで、ワープ０回で辿り着ける全てのマスをque0に挿入すると同時に、そのマスのnumを０に書き換える。

```php

while(!que.empty()){
    pair<int,int> v = que.front();
    que.pop();
    
    int x,y;
    tie(x,y) = v;
    
    if(num[x+1][y]==-1){  //下のマスがまだ訪れていない道なら、訪れて記録する
      num[x+1][y]=p;
      que0.push(make_pair(x+1,y));
      que.push(make_pair(x+1,y));
    }
    
    //上・左・右も同様
  }
```

　そして②。ワープ０で行ける全てのマスからワープを使って行ける25マス（のうち、まだ訪れていない道）をqueとque0に再び挿入。

```php
for(int i = 0; i<t;i++){
    pair<int,int> v = que0.front();
    que0.pop();
    int x,y;
    tie(x,y) = v;
    for(int i = max(0,x-2); i<=min(1010, x+2); i++){
      for(int j = max(0,y-2); j<=min(1010, y+2); j++){
        if(num[i][j]==-1){//もし（i,j）が道で、かつまだ訪れていないとき
          num[i][j]=p;
          que.push(make_pair(i,j));
          que0.push(make_pair(i,j));
        }
      }
    }
  }
```

　後は、これをワープする回数を１ずつ増やして①と②繰り返せばよい。以下自分の提出。

```php
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (ll i = m; i < (n); i++)

int main(){
  int H, W, Sx, Sy, Gx, Gy;
  cin >> H >> W >> Sx >> Sy >> Gx >> Gy;
  vector<vector<int>> num(1010,vector<int>(1010, -2));//そのマスにワープ何回で辿り着けるか記録する
  
  //道の受け取り
  char s;
  rep(i,H){
    rep(j,W){
      cin >> s;
      if(s == '.'){
        num[i+1][j+1] = -1;
      }
    }
  }
  
  //BFSの準備
  queue<pair<int,int>> que0;  
  queue<pair<int,int>> que;
  
  que.push(make_pair(Sx,Sy));
  que0.push(make_pair(Sx,Sy));
  num[Sx][Sy] = 0;
  int p = 0;
  
  while(!que.empty()){
  
    while(!que.empty()){
      pair<int,int> v = que.front();
      que.pop();
    
      int x,y;
      tie(x,y) = v;
    
      if(num[x+1][y]==-1){
        num[x+1][y]=p;
        que0.push(make_pair(x+1,y));
        que.push(make_pair(x+1,y));
      }
      if(num[x-1][y]==-1){
        num[x-1][y]=p;
        que0.push(make_pair(x-1,y));
        que.push(make_pair(x-1,y));
      }
      if(num[x][y+1]==-1){
        num[x][y+1]=p;
        que0.push(make_pair(x,y+1));
        que.push(make_pair(x,y+1));
      }
      if(num[x][y-1]==-1){
        num[x][y-1]=p;
        que0.push(make_pair(x,y-1));
        que.push(make_pair(x,y-1));
      } 
    }
    
    p++;
    int t = que0.size();
    for(int i = 0; i<t;i++){
      pair<int,int> v = que0.front();
      que0.pop();
      int x,y;
      tie(x,y) = v;
      for(int i = max(0,x-2); i<=min(1010, x+2); i++){
        for(int j = max(0,y-2); j<=min(1010, y+2); j++){
          if(num[i][j]==-1){
            num[i][j]=p;
            que.push(make_pair(i,j));
            que0.push(make_pair(i,j));
          }
        }
      }
    }
    
  }
 
  cout << num[Gx][Gy] << endl;
}
```
　こんなの時間内に解けるわけない…

#E問題
　D問題に比べてとっつきやすいと思ったら、TLEとの戦いでした。
　反省点として、爆弾が存在する場所を```vector<vector<bool>> bom```で管理して、爆弾が存在するかどうか毎回```if(bom[i][j])```みたいに判定しようとしたが、これがくそ時間がかかるらしい。
　いろいろ調べた結果、```set```で爆弾があるマスを管理し、```bom.find(調べたいマス)==bom.end()```によって所属判定が簡単に素早く行えると知った。
　以下提出コード。

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

#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (ll i = m; i < (n); i++)


int main(){
  int H, W, M;
  cin >> H >> W >> M;
    
  vector<int> Hi(H, 0);
  vector<int> Wi(W, 0);
  set<pair<int,int>> bom;
  for(int i = 0; i<M; i++){
    int h,w;
    cin >> h >> w;
    Hi[h-1]++;
    Wi[w-1]++;
    bom.insert(make_pair(h-1,w-1));
  }
  
  int max_h = 0;//行の最大値
  int max_w = 0;//列の最大値
  
  //最大値を求める
  for(int i = 0; i<H; i++){
    max_h = max(max_h, Hi[i]);
  }
  for(int i = 0; i<W; i++){
    max_w = max(max_w, Wi[i]);
  }
   
  vector<int> X(0);
  vector<int> Y(0);
  
  //最大値をとる列・行を記録
  for(int i = 0; i<H; i++){
    if(Hi[i] == max_h){
      X.push_back(i);
    }
  }
  for(int i = 0; i<W; i++){
    if(Wi[i] == max_w){
      Y.push_back(i);
    }
  }

  for(auto p: X){
     for(auto q: Y){
        if(bom.find(make_pair(p,q))==bom.end()){
          cout << max_h+max_w << endl;
          return 0;
        }
     }
  }
  
  cout << max_h+max_w-1 << endl;
  return 0;
}
```

Fはいつか挑戦するかも＿φ(￣ー￣ )