C - 高橋君とカード / Tak and Cards
えーすいません、久しぶりに問題見てみたらよくわかりませんでした(忘れるんじゃねぇぞ…)
考察 (入出力例3)
3 6 2 8 7 6 5 9
この中から何個か選んで平均を5にしたい
まず、並び替えても答えが変わらなさそうなので昇順ソートします(典型思考)
2 3 5 6 6 7 8 9
はい
組み合わせ系の問題は7割方DPで解けることが多いです(超主観)なので、DPできないか考えてみます
DPの添字を考える
情報が足りない
まずdp[i] //i番目までで、平均が5になる組み合わせとしてみます。
しかし、これだけでは足りないことがわかります。なぜなら、dp[0]が0で、次の数字が3のとき、dp[1]が1になるのか0になるのかが分からないからです。遷移をするのにはまだ情報量が少ないです。
平均から合計へ
ここで、「平均が〇〇になる組み合わせ」としてしまうと途中で平均が4.5とかになってしまって困るので、「合計が〇〇になる組み合わせ」という風に言い換えてみます。そうするとDPの添字が小数にならなくなるので嬉しいです。
「合計」の添字を追加
一旦dp[i] //i番目までで、合計が〇〇になる組み合わせとしてみます。ここで〇〇の部分もdpの添字に追加したらいいのでは?となります。なので
dp[i][s] //i番目までで、合計がsになる組み合わせという風になります。
「何枚選んだか」の添字を追加
ここで遷移の一番最後、DP配列が全て埋まったあとのことを考えていきます。組み合わせの数はどうやって求めるかというと
1枚選んで、合計が5になる組み合わせ
2枚選んで、合計が10になる組み合わせ
3枚選んで、合計が15になる組み合わせ
…
を足せば良いということが頑張ればわかります。
ここでなぜ「何枚選んだか」の情報が必要かというと、
「合計が15になりました」と言われたときに、
実は4+5+6の形ではなく7+8だった…という可能性があるからです。後者だと平均は7.5になります。「合計がs」という情報だけだと、7+8のパターンを逃してしまう可能性があります。なので、「何枚選んだか」の情報を足すことにします。
この時点でDPの添字は
dp[i][s][k] // i番目までで、k回カードを選んで、合計がsになる組み合わせ
という風になります。もうこれで良さそうな感じがします(適当)。制約的にMLEしないし…
遷移を考える
2 3 5 6 6 7 8 9 (ここからk回選んで合計をsにする組み合わせの数を考えていきたい)
途中のとある時点で止めた時の遷移をイメージしてみます。それ以前の「k回選んで合計をsにする組み合わせの数」は全て求まっています。なので、自分のカードを使ったときと使わなかったときを考えて
自分のカードを使ったとき
k+1回選んで合計をsにする組み合わせの数
自分のカードを使わなかったとき
そのまま遷移(何もしない)
の2通り(実質1つ)の処理を書けば良いことがわかります。
実装
MODで割らない
long longを使う
大きい配列はグローバルな所で宣言する
dp[0][0][0] = 1の話
0番目までで0回選んで合計を0にする組み合わせは1通りなので
という説明では分かりにくいのですが、遷移を考えた時にその1から枝が分かれるように数が増えていくので、元の部分が0だと、どれだけ分かれていっても0のままになっちゃう、と考えると1っぽいなという気分になります(多分この説明は不十分)
code:sample.cpp
using namespace std;
typedef long long int ll;
// 配列が大きいのでグローバル変数にしてます、あとlong longも忘れずに
ll dp55552600 = {}; // i番目までで、k回選んで合計をsにする組み合わせの数 // ====================================================================
int main() {
ll n, a;
cin >> n >> a;
vector<ll> v(n);
for (int i = 0; i < n; i++) cin >> vi; // 俗に言う配るDP
for (int i = 0; i <= n; i++) {
for (int k = 0; k <= 50; k++) {
for (int s = 0; s <= 2500; s++) {
}
}
}
ll ans = 0;
for (int k = 1; k <= n; k++)
ans += dpnka * k; // k回選んで合計がa*k(つまり平均はa)の組み合わせの数を足す cout << ans << endl;
}