ABC045 ARC061 の問題を解いてみました


## A問題
https://atcoder.jp/contests/abc045/tasks/abc045_a

台形の面積を求める問題です。
上底は$a$ ,下底は$b$ ,高さは$h$ として与えられます。
台形の面積の公式は、$（上底+下底) \times 高さ \div 2$ であり、それをプログラムします。
~~~C++
#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問題
https://atcoder.jp/contests/abc045/tasks/abc045_b

Aさん,Bさん,Cさんが a,b,cと書かれたカードを持っている。(文字列で与えられる)
Aさんのターンから始まり、自分のターンならば先頭のカードを捨てて、
捨てたカードにかかれていた文字の人のターンになる。

というゲームをするので、誰が勝つかを出力してくださいという問題です。


この問題で注意すべき点は、カードが0枚になったときに勝利ではなく、
カードが0枚の状態でターンになれば勝利だという点です。
それを踏まえて繰り返しでこのゲームをシュミレーションして、答えを求めます。
~~~C++
#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問題 
https://atcoder.jp/contests/abc045/tasks/arc061_a

1~9の数字のみで構成される文字列sが与えられます。
文字の間にいくつか <code>+</code> を入れられるので、<code>+</code> を入れることによってできる文字列を数式とみなして、作成できる全ての数式の和を出力する問題です。
なお、制約は $1\leqq |s|\leqq 10$ です。

この問題は、<code>+</code>を入れるか入れないかを 0と1で表すことによって、
bit全探索で解くことができます。
sの長さの制約が小さいため、TLEを回避できます。

(ch - '0' で文字を数値に変換できます。)

bit全探索について詳しくは

https://qiita.com/karaju/items/bb722574a01c837e1a71#bit%E5%85%A8%E6%8E%A2%E7%B4%A2


~~~C++
#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問題
https://atcoder.jp/contests/abc045/tasks/arc061_b

左から$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$の値を変更することで答えを求められます。

~~~C++
#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;
  }
}
~~~