ABC044
A問題
最初の$K$泊までは、1泊あたり$X$円、$K+1$泊目以降は、1泊あたり$Y$円かかる旅館に、$K$泊するとかかる金額を出力します。
宿泊日数の繰り返しを作って、その日の宿泊料金が$X$円か$Y$円かを判定しましょう。
#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問題
文字列wにおいてどの文字も偶数回出てくるかどうかを判定します。
aからzの場合をすべて試します。
文字列の長さが100文字以下なので、計算量を気にせずにこの方法を
取ることができます。
#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問題
数字が書かれたN枚のカード($x_1,x_2,...,x_n$)からいくつかのカードを選び、
数字の合計の平均を$A$にする方法は何通りあるかを求めます。
bit全探索での部分点
$1\leqq N \leqq 16$ の場合についてACできれば、部分点を獲得できます。
部分点の獲得には、bit全探索を用います。
カードを選ぶか選ばないかを、1,0で表す(2進数)と、
全てのカードの組み合わせは$2^n$になります。
これらを繰り返しを用いて試すと、部分点を獲得できます。
bit全探索について詳しくは
#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通り)
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について詳しくは
全てのカードから$i$枚選んだとき、平均が$a$になる
組み合わせの数を繰り返しで求めると、この問題は解くことができます。
#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
あとで