yukicoder No.412 花火大会

問題

問題概要

組み合わせの数え上げ

解法

まず、すべてソートしてく。全探索をして、それぞれの家族がどのマットを使うかを決める。それが条件を満たしたものであれば、ほかのものは選ぶ選ばないの選択がある。
dpのほうがわかりやすいな。状態数は2つで、1つは、何枚目までを考えているか、もう一つは、条件を満たしている数である。 dp[i][j] := i番目のマットまでで考えて、j=1ならBのマットは条件を満たし、j=2ならBCのマットは条件を満たし、j=3ならすべてのマットの条件を満たすとしてやる。
漸化式は、i番目のマットが、新たに次の条件を満たす大きさであるなら(j=1なら次はc以上の大きさであれば条件を満たす)、i番目のマットを選べば新たに条件を満たし、選ばなければ新たに条件は増えないので、
dp[i + 1][j + 1] += dp[i][j];//選択する
dp[i + 1][j] += dp[i][j];//選択しない
となる。
条件を満たさないときは、i番目の選択の有無にかかわらず条件を満たすことはないので、
dp[i + 1][j] += 2 * dp[i][j];//選択するしないの2通り
となる

ミス

これは典型的dpなんですね。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int main(void){
    vector<int> s(3);
    int n;
    rep(i, 3) cin >> s[i];
    cin >> n;
    sort(s.begin(), s.end());

    vector<int> e(n);
    rep(i, n) cin >> e[i];
    sort(e.begin(), e.end());

    ll ans = 0;
    for (int i = 0; i < n; ++i){
        for (int j = i + 1; j < n; ++j){
            for (int k = j + 1; k < n; ++k){
                if(s[0] <= e[i] && s[1] <= e[j] && s[2] <= e[k]){
                    //上記の３つ以外で条件を満たすものは使う使わないの２通りの方法を選ぶことができる
                    ans += pow(2, i);
                }
            }
        }
    }
    printf("%lld\n", ans);
}

dp

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

//dp[i][j] := i番目のマットまでで考えて、
//j=1ならBのマットは条件を満たし、j=2ならBCのマットは条件を満たし、
// j=3ならすべてのマットの条件を満たす
int dp[50][4];
int main(void){
    vector<int> s(3);
    int n;
    rep(i, 3) cin >> s[i];
    cin >> n;
    sort(s.begin(), s.end());

    vector<int> e(n);
    rep(i, n) cin >> e[i];
    sort(e.begin(), e.end());

    dp[0][0] = 1;
    for (int i = 0; i < n; ++i){
        for (int j = 0; j <= 3; ++j){
            if(j < 3 && s[j] <= e[i]){//j個目に条件を満たすもととして選択可
                dp[i + 1][j + 1] += dp[i][j];//選択する
                dp[i + 1][j] += dp[i][j];//選択しない
            }else{//選択しても条件は満たさない
                dp[i + 1][j] += 2 * dp[i][j];//選択するしないの2通り
            }
        }
    }

    printf("%lld\n", dp[n][3]);
    return 0;
}