Editorial for Atcoder Educational DP Contest I - Coins

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ncduy0303

Gọi ~dp[i][j]~ là xác suất để có ~j~ mặt ngửa sau khi tung ~i~ đồng xu đầu tiên. Xác suất này có thể được tính bằng cách lấy tổng xác suất của hai trường hợp:

  • Đồng xu thứ ~i~ là mặt ngửa, và ~i-1~ đồng xu trước đó có ~j-1~ mặt ngửa. Xác suất của trường hợp này là ~dp[i-1][j-1] \cdot p[i]~
  • Đồng xu thứ ~i~ là mặt sấp, và ~i-1~ đồng xu trước đó có ~j~ mặt ngửa. Xác suất của trường hợp này là ~dp[i-1][j] \cdot (1-p[i])~

Do đó, công thức quy hoạch động là:

~dp[i][j]=dp[i−1][j−1] \cdot p[i]+dp[i−1][j] \cdot (1−p[i])~

Độ phức tạp: ~O(N^{2})~

Code tham khảo

#include<bits/stdc++.h>

using namespace std;

long double dp[3001][3001];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n; cin >> n;

    vector<long double> p(n + 1);
    for(int i = 1; i <= n; ++i) cin >> p[i];

    int leastHeads = n / 2 + 1;

    for (int i = 0; i <= n; ++i) dp[i][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= leastHeads; ++j) {
            dp[i][j] = dp[i - 1][j - 1] * p[i] + dp[i - 1][j] * (1 - p[i]);
        }
    }

    cout << fixed << setprecision(10) << dp[n][leastHeads] << endl;
}

Comments

Please read the guidelines before commenting.


  • 6
    tandochuyentin2022  commented on April 13, 2024, 2:50 a.m.

    Một cách làm khác dễ hiểu hơn của mình với việc tính tổng xác suất những lần số mặt của > n/2:

    // problem "atcoderdpi" // created in 14:27:21 - Fri 12/04/2024

    include <bits/stdc++.h>

    using namespace std;

    int n, k; long double dp[3001][3001], p[3000];

    int32t main() { iosbase::syncwithstdio(false); cin.tie(NULL);

    cin >> n; for(int i = 1; i <= n; i++) cin >> p[i];

    k = n / 2 + 1;

    dp[1][0] = 1 - p[1]; dp[1][1] = p[1];

    for(int i = 2; i <= n; i++) { for(int j = 0; j <= i; j++) { dp[i][j] = dp[i - 1][j] * double(1 - p[i]); if(j > 0) dp[i][j] += dp[i - 1][j - 1] * p[i]; // else // dp[i][j] += dp[i-1][j] * p[i]; } }

    double ans = 0; for(int i = n; i >= k; i--) ans += dp[n][i];

    cout << fixed << setprecision(10) << ans; }


    • 0
      vlthhiep08  commented on Jan. 9, 2025, 10:09 p.m.

      code của b đúng ý mình luon, dễ hiểu, cách của ad ngẫm mãi ko ra


  • 2
    khanhss  commented on May 1, 2023, 11:16 a.m. ← edit 2

    biến cố đối ấy bn. Nếu giả sử xác xuất xảy ra pi nào đó là 40% tức là 0,4 thì ko xảy ra pi là 60% tức là 100 % - 40% tức là 1 - 0,4


  • 4
    tnhu_0508  commented on Aug. 1, 2022, 6:08 a.m.

    mọi người cho mình cái dòng leastHeads với ạ , tại sao mình lại chỉ duyệt tới đó thoi vậy ạ


    • 2
      damtrungduc  commented on Oct. 7, 2022, 8:56 a.m.

      vì xu ngửa lớn hơn xu sấp nên chỉ cần lượng xu ngửa lớn hơn quá bán là đc


      • -1
        quyet  commented on Aug. 5, 2023, 1:30 p.m.

        sao ko chạy đến n nhỉ :< vì từ n/2+1 đến n nó cx lớn hơn 1 nửa mà nhỉ mình ch hiểu lắm


  • 6
    Rukashi  commented on Feb. 15, 2022, 8:49 a.m.

    Cho mình hỏi là vì sao xác suất tất cả các mặt đều sấp từ 1-n là 1 vậy :(