0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Last updated at Posted at 2023-12-29

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$にする方法は何通りあるかを求めます。
なお、重要な制約としては、$1\leqq N \leqq 50$ があります。

bit全探索での部分点

部分店の制約は、 $1\leqq N \leqq 16$ です。
bit全探索では、200点のみとなります。

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

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

(bit[n]をかけると、0なら0で、1なら変化しない)

部分点のコード
#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

あとで

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?