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つあるということです。
左から6マス目に黒のコマを打つと、下のようになります。
すると、グループが3つになります。
(コマを打つことによって、2つのグループを 1つのグループにしています。)
その操作を繰り返すと、以下のようになります。
最終的に、グループが1つになります。
つまり、この盤面はグループを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問題
まず、最大の利益を出すには、最も安く買って、最も高く売れば良いです。
3 2
100 50 200
例えば、入力例1 ならば 50円で買って 200円で売れば 最大の利益を出すことができます。
その利益を 1円 でも下げるには、 コスト1 で、 50円 を 51 円 にすれば良いです。
(200円 を 199 円 にしても良い。)
すると、利益が 150円 から 149円 に減少します。
じゃあ、すべての場合で コスト1 で利益を減らせるのではないかということですが、それは正しくありません。
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;
}