EDPC-I「Coins」

Coins

コンテスト中の考察

• 状態変数を考える。dp[表の枚数][裏の枚数]を持つと良さそう。
• dp[i][j]: 表i枚、裏j枚を引く割合という意味とする
• 簡単な遷移を考える。すると、以下のようになる

// おもて
dp[i+1][j] ← dp[i][j]

// うら
dp[i][j+1] ← dp[i][j]

• 値を絡めた遷移を考える。すると以下のようになる（これ間違ってるんだけどね）
• 確率だからちょっと複雑に思えるけど、今の状態と次の状態のみを考えればいいだけなので難しく考える必要はない
• 表が出た時は、表i枚、裏j枚の確率に表が出る確率をかける。
• 裏が出た時は、表i枚、裏j枚の確率に裏が出る確率をかける。

// おもて
dp[i+1][j] += dp[i][j] * p[i];
// うら
dp[i][j+1] += dp[i][j] * (1 - p[j]);

コード（間違ってるけど）

• 考察によって得られるコードは以下の通り。でもサンプルと合わない。
• 何もわからないままコンテストが終了した

#include <bits/stdc++.h>
using namespace std;

#define int long long

int N;
double p[3333];
double dp[3333][3333]; // dp[i][j]: 表i枚、裏j枚が出る確率

signed main() {
  // 入力
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> p[i];
  }

  dp[0][0] = 1;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      // おもて
      dp[i+1][j] += dp[i][j] * p[i];
      // うら
      dp[i][j+1] += dp[i][j] * (1 - p[j]);
    }
  }

  double ans = 0;
  for (int i = N/2+1; i <= N; i++) {
    int j = N - i;
    ans += dp[i][j];
  }

  printf("%.10f\n", ans);

  return 0;
}

間違えてた部分

• 値を絡めた遷移の考察が間違えていた。

// おもて
dp[i+1][j] += dp[i][j] * p[i];
// うら
dp[i][j+1] += dp[i][j] * (1 - p[j]);

• p[i], p[j]を使ってるのがまずい。例えばi = 2, j = 2のとき、遷移は以下のようになる。注目するポイントは、

// おもて
dp[3][2] += dp[2][2] * p[2];
// うら
dp[2][3] += dp[2][2] * (1 - p[2]);

• なぜならdp[i][j]: 表がi枚、裏がj枚出る確率という意味なので、コインは合計でi+j枚使ったことになる。
• だからなんなんだ。よくわからなくなってきた。はい、このDPわかりません。終了
• 以下の遷移が正しい遷移（satanicさんに教えてもらいました）（理解はしてないです）

// おもて
dp[i+1][j] += dp[i][j] * p[i+j];
// うら
dp[i][j+1] += dp[i][j] * (1 - p[i+j]);

間違えてた部分を直したコード

#include <bits/stdc++.h>
using namespace std;

#define int long long

int N;
double p[3333]; // コインの表が出る確率
double dp[3333][3333];

signed main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> p[i];
  }

  dp[0][0] = 1; // DPテーブルを初期化
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (i + j > N) continue;
      // おもて
      dp[i+1][j] += dp[i][j] * p[i+j];
      // うら
      dp[i][j+1] += dp[i][j] * (1 - p[i+j]);
    }
  }

  double ans = 0;
  for (int i = N/2 +1; i <=N; i++) {
    int j = N - i;
    ans += dp[i][j];
  }

  printf("%.10f\n", ans);

  return 0;
}

もう少し考えやすいDPをする

• 先ほどはdp[表][裏]で考えた。だが、これはちょっと考えづらい。DPの状態変数にインデックスを持たせないと頭がぶっ壊れる。
• なので、dp[表][裏]にインデックスの状態を加える
• すると、dp[使ったコインの枚数][表が出た枚数][裏が出た枚数]となる。使ったコインの枚数がインデックスにあたる。
• しかし、これはdp[3000][3000][3000]みたいな配列を作る必要がある。これはメモリ的に厳しそう。
• なので、もう少しDPを改善する必要がある
• DPに必要な情報を考え直す。すると、「使ったコインの枚数」と「出た表の枚数」の情報でDPできそうだなーってなる。
• dp[コインをi枚使った][表がj枚出た]みたいな感じで
• 次になんとなくの遷移を考える。以下のようになる。pの添字は0-indexedで大丈夫そう

// 表が出る
dp[i+1][j+1] ← dp[i][j] * p
// 裏が出る
dp[i+1][j] ← dp[i][j] * (1 - p)

考えやすいDPのコード

#include <bits/stdc++.h>
using namespace std;

#define int long long

int N;
double p[3333]; // コインの表が出る確率
double dp[3333][3333]; // dp[i][j]: コインをi枚使って、表がj枚でる確率

signed main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> p[i];
  }

  dp[0][0] = 1; // DPテーブルを初期化
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      // おもて
      dp[i+1][j+1] += dp[i][j] * p[i];
      // うら
      dp[i+1][j] += dp[i][j] * (1 - p[i]);
    }
  }

  double ans = 0;
  for (int i = N/2 +1; i <=N; i++) {
    ans += dp[N][i];
  }

  printf("%.10f\n", ans);

  return 0;
}

要点

• DPの状態変数に「データ（配列）をどこまで使ったか」という情報を持たせた方が考えやすい。じゃないと頭ぶっ壊れる
  • 今回の場合、dp[コイン総数][表の枚数]で考えると良かった。こっちの方が入力配列の添字的にも直感的にかける。
  • dp[i][...]: i番目までみたときほげほげのよくあるパターン。
  • dp[表][裏]には配列の添字（コインを何枚まで使ったかという情報）が含まれてないので破滅する
• 確率の計算は、今の値に次の確率をかけてるだけ
  • 状態がたくさんあって複雑に考えてしまいそうになる。けどそんなに難しく考えなくていい

メモ

• 全体の枚数を持たせるのは思いつかなかった。使わなくてもできるけど、思いつく状態変数の幅を広げたい。