ABC044 ARC060 の問題を解いてみました

## ABC044
### A問題
https://atcoder.jp/contests/abc044/tasks/abc044_a

最初の$K$泊までは、1泊あたり$X$円、$K+1$泊目以降は、1泊あたり$Y$円かかる旅館に、$K$泊するとかかる金額を出力します。
宿泊日数の繰り返しを作って、その日の宿泊料金が$X$円か$Y$円かを判定しましょう。
~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by Karaju

int main() {
	int n, k, x, y, cost = 0;
	cin >> n >> k >> x >> y;
	for (int i = 0; i < n; i++) { //宿泊日数 繰り返す
		if (i < k) { //最初のK泊までなら
			cost += x;
		}
		else {
			cost += y;
		}
	}
	cout << cost << endl;
	
	return 0;
}
~~~
### B問題
https://atcoder.jp/contests/abc044/tasks/abc044_b

文字列wにおいてどの文字も偶数回出てくるかどうかを判定します。
aからzの場合をすべて試します。
文字列の長さが100文字以下なので、計算量を気にせずにこの方法を
取ることができます。
~~~C++
#include <bits/stdc++.h>
using namespace std;
//Created by karaju

int main() {
	string w;
	cin >> w;
	int count = 0;
	for (char t = 'a'; t <= 'z'; t++) { //アルファベット全てで試す
		for (int i = 0; i < w.size(); i++) {
			if (w[i] == t) { 
				count++; // t という文字の数を数える
			}
		}
		if (count % 2 == 1) { //奇数回だったなら
			printf("No");
			return 0;
		}
	}
	printf("Yes");
}
~~~


### C問題
https://atcoder.jp/contests/abc044/tasks/arc060_a

数字が書かれたN枚のカード($x_1,x_2,...,x_n$)からいくつかのカードを選び、
数字の合計の平均を$A$にする方法は何通りあるかを求めます。

#### bit全探索での部分点
$1\leqq N \leqq 16$ の場合についてACできれば、部分点を獲得できます。
部分点の獲得には、bit全探索を用います。

カードを選ぶか選ばないかを、1,0で表す(2進数)と、
全てのカードの組み合わせは$2^n$になります。
これらを繰り返しを用いて試すと、部分点を獲得できます。

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(void){
  int n, a;
  cin >> n >> a;
  int x[n];
  for(int i = 0; i < n; i++) cin >> x[i];
  
  int ans = 0;
  for(int i = 1; i < (1 << n); i++){ //2^n 回繰り返す
    double sum = 0;
    int count = __builtin_popcount(i);
    //i を2進数に変換したときの1の数を返す
    //つまりは、count に 選ぶカードの数を代入する
    
    for(int j = 0; j < n; j++){
      if(i & (1 << j)){ //iを2進数に変換したもののj桁目が 1 なら
        sum += x[j]; //sum に カードに書かれた数字を加える
      }
    }
    
    if(sum / count == a) ans++;
    //カードの平均がaなら、組み合わせの数にカウントする
  }
  cout << ans << endl;
}

~~~
この方法では、Nの値が大きいと正しい答えを求められません。

#### DP(動的計画法)での満点
この問題を解くにはDPというアルゴリズムを用います。
$dp[i][j][k]$  という3次元配列を考えます。
($i枚目までからj枚選び、合計がkになる組み合わせの数$)
$dp[0][0][0]$ は1になります。(0枚選び、合計は0で、1通り)

~~~C++
dp[i + 1][j][k] += dp[i][j][k];
dp[i + 1][j + 1][k + li[i]] += dp[i][j][k];
~~~
上はカードを選ばない場合で、下は選ぶ場合です。
上は$i$枚目を選ばないため、$i$枚目までの場合と、
$i+1$枚目までの場合の組み合わせの数は変わらないです。
下は 選ぶ枚数の合計の$j$を$+1$して、
合計に$i$番目のカードの番号を加えます。

DPについて詳しくは

https://qiita.com/karaju/items/bb722574a01c837e1a71#%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95-dp


全てのカードから$i$枚選んだとき、平均が$a$になる
組み合わせの数を繰り返しで求めると、この問題は解くことができます。
~~~C++:正解コード
#include <bits/stdc++.h>
using namespace std;
//Created by karaju

int main() {
	int n, a;
	long long ans = 0;
	cin >> n >> a;
	int li[50];
	for (int i = 0; i < n; i++) {
		cin >> li[i];
	}
 
	long long dp[51][51][10000];
	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++) { // i 枚目までから
		for (int j = 0; j < n; j++) { // j 枚選び
			for (int k = 0; k < 50 * 50; k++) { //合計が k
				dp[i + 1][j][k] += dp[i][j][k];
				dp[i + 1][j + 1][k + li[i]] += dp[i][j][k];
			}
		}
	}
	for (int i = 0; i < n; i++) {
		ans += dp[n][i + 1][(i + 1)*a];
        // 選んだ枚数 * a が合計になる
        // つまり、平均が a の組み合わせの数を数える
	}
	cout << ans << endl;
	
	return 0;
}
~~~


### D
https://atcoder.jp/contests/abc044/tasks/arc060_b

あとで