ABC047 ARC063 の問題を解いてみました

## A問題
https://atcoder.jp/contests/abc047/tasks/abc047_a

問題を言い換えると、つまりは
$2個のパックのキャンディーの個数 = 1個のパックのキャンディーの個数$
が成り立つかを判定すれば良いです。
~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  int a, b, c;
  cin >> a >> b >> c;
  if(a == b + c || b == a + c || c == a + b){
  //2個のパックのキャンディーの個数 = 1個のパックのキャンディーの個数が成り立つか確かめる
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}
~~~

また、
$最もキャンディーが入っているパックのキャンディーの個数 = その他のパックのキャンディーの個数$
が成り立つかを判定すれば良いので、ソートを使っても解けます。
~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  int candy[3];
  for(int i = 0; i < 3; i++) cin >> candy[i];
  sort(candy, candy + 3);
  
  if(candy[0] + candy[1] == candy[2]){
  //最もキャンディーが入っているパックのキャンディーの個数 = その他のパックのキャンディーの個数 が成り立つか試す
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}
~~~

## B問題
https://atcoder.jp/contests/abc047/tasks/abc047_b

この問題は、塗りつぶしを実際にシミュレーションすることなどで解くことができます。

* $a_i=1$ のときは長方形の $x<x_i$をみたす領域
* $a_i=2$ のときは長方形の $x>x_i$をみたす領域
* $a_i=3$ のときは長方形の $y<y_i$をみたす領域
* $a_i=4$ のときは長方形の $y>y_i$をみたす領域

を黒く塗ります。

塗るべき領域を黒く塗る処理を if文 などを使い、実際に実装してみましょう。

~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  int w, h, n;
  cin >> w >> h >> n;
  bool plane[w][h];
  //左下の座標が(i,j)であるマスが塗られているかを記録する配列
  for(int i = 0; i < w; i++) for(int j = 0; j < h; j++) plane[i][j] = false;
  
  for(int i = 0; i < n; i++){
    int x, y, a;
    cin >> x >> y >> a;
    if(a == 1){
      for(int xx = 0; xx < w; xx++){
        for(int yy = 0; yy < h; yy++){
          if(xx < x){ //塗るべき領域なら
            plane[xx][yy] = true;
          }
        }
      }
    }
    else if(a == 2){
      for(int xx = 0; xx < w; xx++){
        for(int yy = 0; yy < h; yy++){
          if(xx >= x){ //塗るべき領域なら
            plane[xx][yy] = true;
          }
        }
      }
    }
    else if(a == 3){
      for(int xx = 0; xx < w; xx++){
        for(int yy = 0; yy < h; yy++){
          if(yy < y){ //塗るべき領域なら
            plane[xx][yy] = true;
          }
        }
      }
    }
    else{
      for(int xx = 0; xx < w; xx++){
        for(int yy = 0; yy < h; yy++){
          if(yy >= y){ //塗るべき領域なら
            plane[xx][yy] = true;
          }
        }
      }
    }
  }
  
  int ans = 0;
  for(int i = 0; i < w; i++) for(int j = 0; j < h; j++){
    if(!plane[i][j]) ans++;
  }
  cout << ans << endl;
}
~~~

また、角の座標を記録しておくことでも解くことができます。

~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  int w, h, n;
  cin >> w >> h >> n;
  int x = 0, y = 0;
  
  for(int i = 0; i < n; i++){
    int X, Y, A;
    cin >> X >> Y >> A;
    if(A == 1) x = max(x, X);
    if(A == 2) w = min(w, X);
    if(A == 3) y = max(y, Y);
    if(A == 4) h = min(h, Y);
  }
  
  cout << max(w - x, 0) * max(h - y, 0) << endl;
}
~~~

## C問題
https://atcoder.jp/contests/abc047/tasks/arc063_a

例えば、下のような盤面があったとします。
同じ色の集合をグループと呼ぶとします。
下の盤面では、グループが4つあるということです。

![Screenshot 2023-12-31 19.33.03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3602077/16c327c1-fbeb-e1b5-369f-fa73ae1fcbbd.png)

左から6マス目に黒のコマを打つと、下のようになります。
すると、グループが3つになります。
(コマを打つことによって、2つのグループを 1つのグループにしています。)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3602077/ed2d69ba-3d59-6205-555f-4efcc8e07b31.png)



その操作を繰り返すと、以下のようになります。
最終的に、グループが1つになります。

![Screenshot 2023-12-31 19.35.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3602077/ac6fb59b-23a2-eac0-f8b0-321706331113.png)

つまり、この盤面はグループを1つにするのに、3回の操作が必要ということです。
この操作の回数を求める方法を考えます。

上でも書いたように、2つのグループを 1回の操作で 1つのグループにまとめることができます。
なので、必要な操作の回数は、$グループの数 - 1$ で求められます。

~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  string s;
  cin >> s;
  
  char color = 'A';
  int group = 0;
  for(int i = 0; i < s.size(); i++){
    if(color != s[i]){
      color = s[i]; //何色だったか記録する変数
      group++; //グループの数を数える
    }
  }
  
  cout << group - 1 << endl;
}
~~~


## D問題
https://atcoder.jp/contests/abc047/tasks/arc063_b

まず、最大の利益を出すには、最も安く買って、最も高く売れば良いです。
~~~:入力例1
3 2
100 50 200
~~~
例えば、入力例1 ならば 50円で買って 200円で売れば 最大の利益を出すことができます。
その利益を 1円 でも下げるには、 コスト1 で、 50円 を 51 円 にすれば良いです。
(200円 を 199 円 にしても良い。)
すると、利益が 150円 から 149円 に減少します。

じゃあ、すべての場合で コスト1 で利益を減らせるのではないかということですが、それは正しくありません。

~~~:入力例2
5 8
50 30 40 10 20
~~~
入力例2 の場合を考えてみましょう。
最大の利益を出す方法は、 30円で買って 40円で売る という方法と、
10円で買って 20円で売る という方法の2つがあります。
仮に、町2 での りんごの価格 を 31円に上げて、利益を減らしても、
町4 で 10円 で買って、 町5 で 20円 で売れば 最大の利益を上げられます。
町4 の りんごの価格を 11円に上げて、利益を減らすことで初めて、利益を下げることができます。

つまりは、最大の利益を出す方法を全て潰せばいいので、答えは最大の利益を出す方法の数になります。



~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  long long n, t;
  cin >> n >> t;
  long long a[n];
  for(int i = 0; i < n; i++) cin >> a[i];
  long long cheap = a[0], best = 0, count = 0;
  
  for(int i = 1; i < n; i++){
    if(cheap > a[i]){
      //最も安いりんごの価格を記録する
      cheap = a[i];
    }
    else if(a[i] - cheap == best){ //もし、出せる利益が最大なら
      count++;
      //その利益を出す方法の数を記録しておく
    }
    else if(a[i] - cheap > best){ //もし、出せる利益が最大を更新するなら
      //最大の利益額を記録する
      best = a[i] - cheap;
      //その利益を出す方法の数を1 にする
      count = 1;
    }
  }
  
  cout << count << endl;
}
~~~