A問題
台形の面積を求める問題です。
上底は$a$ ,下底は$b$ ,高さは$h$ として与えられます。
台形の面積の公式は、$（上底+下底) \times 高さ \div 2$ であり、それをプログラムします。
#include <bits/stdc++.h>
using namespace std;
//Created by Karaju
int main() {
int a, b, h;
cin >> a >> b >> h;
cout << (a + b) * h / 2 << endl;
}
B問題
Aさん,Bさん,Cさんが a,b,cと書かれたカードを持っている。(文字列で与えられる)
Aさんのターンから始まり、自分のターンならば先頭のカードを捨てて、
捨てたカードにかかれていた文字の人のターンになる。
というゲームをするので、誰が勝つかを出力してくださいという問題です。
この問題で注意すべき点は、カードが0枚になったときに勝利ではなく、
カードが0枚の状態でターンになれば勝利だという点です。
それを踏まえて繰り返しでこのゲームをシュミレーションして、答えを求めます。
#include <bits/stdc++.h>
using namespace std;
//Created by karaju
int main() {
string a, b, c;
int aa = 0, bb = 0, cc = 0;
//aaはaさんが捨てたカードの枚数。 bb, ccも同様。
cin >> a >> b >> c;
char turn = 'a'; //誰のターンか
while (true) {
if (turn == 'a') {
if (aa == a.size()) { // a さんが 0枚なら
cout << "A" << endl;
break;
}
turn = a[aa];
aa++;
}
else if (turn == 'b') {
if (bb == b.size()) { // b さんが 0 枚なら
cout << "B" << endl;
break;
}
turn = b[bb];
bb++;
}
else {
if (cc == c.size()) { // c さんが 0 枚なら
cout << "C" << endl;
break;
}
turn = c[cc];
cc++;
}
}
return 0;
}
C問題
1~9の数字のみで構成される文字列sが与えられます。
文字の間にいくつか + を入れられるので、+ を入れることによってできる文字列を数式とみなして、作成できる全ての数式の和を出力する問題です。
なお、制約は $1\leqq |s|\leqq 10$ です。
この問題は、+を入れるか入れないかを 0と1で表すことによって、
bit式全探索で解くことができます。
計算量も、$O(2^N)$になるが、sの長さの制約が小さいため、TLEを回避できます。
(ch - '0' で文字を数値に変換できます。)
bit全探索について詳しくは
#include <bits/stdc++.h>
using namespace std;
//Created by karaju
int main() {
string s;
cin >> s;
long long ans = 0, b = 0, c = 0;
for (int i = 0; i < (1<<(s.length()-1)); i++) {
b = 0; //式の値を記録する
c = s[0] - '0'; //項の数字を記録する
//'0'で引くことによって、s[0]をcharからintにする
for (int j = 0; j < s.length() - 1; j++) {
if (i & (1 << j)) { //もし+を入れるなら
b += c;
c = 0;
}
c = c * 10 + s[j + 1] - '0';
// それぞれの項の数字を計算する
}
b += c;
ans += b;
}
cout << ans << endl;
return 0;
}
D問題
左から$x$列目、上から$y$行目のマスを$(x,y)$と表します。
そして、そのマスを中心とした$3×3$のマスに含まれる黒いマスの数を$b(x,y)$と表します。$(1 < x < W, 1 < y < H,$端のマスを中心とした四角は存在しないため$)$
それぞれのマスの$b(x,y)$を表すことは、配列のサイズの関係でできません。
ここで考察をしてみます。
あるマスを黒く塗りつぶしたとき、その操作が影響するのは周囲9マスの$b(x,y)$です。
$0≤N≤min(10^5,H×W)$ という制約より、操作が影響するマスの数は最大でも$9 \times 10^5$個になるということがわかります。
そのため、操作が影響するマスだけ$b(x,y)$の値を保存しておくことはできます。C++のmapなどを使用して保存しましょう。
操作が影響しなかったマスは、もちろん $b(x,y) = 0$ です。
次に、黒いマスが$j$個ある四角形の数を数える方法を考えます。
黒いマスが$j$個ある四角形の数を記録する配列$Ans_i \ (0 \leq i \leq 9)$ を用意します。
すべてのマスが白い最初の状態では、$b(x, y) = 0$ となる$x,y$の組み合わせは、$(H - 2) \times (W - 2)$ で求められます。
つまり、$Ans_0 = (H - 2) \times (W - 2)$ となります。(端を中心とする四角は存在しないため)
そして、白いマスが黒いマスになるとき、周囲9マスの$b(x,y)$の値を$+1$して、その分配列$Ans$の値を変更することで答えを求められます。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//Created by karaju.
const int dy[] = {-1, -1, -1, 0, 1, 1, 1, 0, 0};
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1, 0};
signed main(){
ll h, w, n;
cin >> h >> w >> n;
vector<ll> ans(10, 0);
//黒いマスが周囲にいくつあるかを保存する配列
ans[0] = (h - 2LL) * (w - 2LL);
map<pair<int,int>,int> black;
for(int i = 0; i < n; i++){
int a, b;
cin >> a >> b;
for(int j = 0; j < 9; j++){ // 3 * 3 のマスについて
int y = a + dy[j], x = b + dx[j];
if(y >= 2 && x >= 2 && y <= h - 1 && x <= w - 1){
//解説でいう b(x, y)
ans[black[{x, y}]]--;
black[{x, y}]++;
ans[black[{x, y}]]++;
}
}
}
for(auto p : ans){
cout << p << endl;
}
}