0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Last updated at Posted at 2023-12-31

A問題

問題を言い換えると、つまりは
$2個のパックのキャンディーの個数 = 1個のパックのキャンディーの個数$
が成り立つかを判定すれば良いです。

#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;
  }
}

また、
$最もキャンディーが入っているパックのキャンディーの個数 = その他のパックのキャンディーの個数$
が成り立つかを判定すれば良いので、ソートを使っても解けます。

#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問題

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

  • $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文 などを使い、実際に実装してみましょう。

#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;
}

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

#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問題

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

Screenshot 2023-12-31 19.33.03.png

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

image.png

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

Screenshot 2023-12-31 19.35.20.png

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

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

#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問題

まず、最大の利益を出すには、最も安く買って、最も高く売れば良いです。

入力例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円に上げて、利益を減らすことで初めて、利益を下げることができます。

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

#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;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?