テクい！「D - サイコロ」（Typical DP Contest）

Wormholex 6面ダイス20個セット 14mm ラウンドコーナー クリア サイコロ 10色（レッド、浅いブルー、オレンジ、黄色、紫色、濃いブルー、バラ色、ピンク、蛍光グリーン、黄緑色） 1枚収納袋付き

Quiz

https://tdpc.contest.atcoder.jp/tasks/tdpc_dice

AC

https://tdpc.contest.atcoder.jp/submissions/8804908

テクい点

• サイコロN回分のdpテーブルを用意するとメモリが足りないので、2回分だけ用意して使い回す
  • cur, next
  • memset
• 素因数分解がsqrt(D)では間に合わない
  • 2, 3, 5で割れるかだけ知りたいのでlog(D)で求められる
• dpテーブルはlong longで持つとオーバーフローするのでdoubleで持つ
  • ちなみに最初はlong doubleとしていて、どちらでも通った
  • doubleの方が2倍速かった（定数倍効く）
• dpテーブルの状態の持ち方
  • dp[i][2の指数][3の指数][5の指数]

Code

double dp[2][201][101][101];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N, D;
    cin >> N >> D;

    ll cur = 0;
    ll next = 1;
    dp[0][0][0][0] = 1;
    rep(i, N){
      memset(dp[next], 0, sizeof(dp[next]));
      // i回目なら、今までに出た2の数は
      ll num2_max = 2*i;
      ll num3_max = i;
      ll num5_max = i;
      
      rep(j, num2_max+1){
        rep(k, num3_max+1){
          rep(l, num5_max+1) if(dp[cur][j][k][l]){
            dp[next][j][k][l] += dp[cur][j][k][l]; // 1
            dp[next][j+1][k][l] += dp[cur][j][k][l]; // 2
            dp[next][j][k+1][l] += dp[cur][j][k][l]; // 3
            dp[next][j+2][k][l] += dp[cur][j][k][l]; // 4
            dp[next][j][k][l+1] += dp[cur][j][k][l]; // 5
            dp[next][j+1][k+1][l] += dp[cur][j][k][l]; // 6
          }
        }
      }
      swap(cur, next);
      // cur == 1
      // next == 0
    }

    ll d = D;
    int two = 0, three = 0, five = 0;
    while(d % 2 == 0) two++, d /= 2;
    while(d % 3 == 0) three++, d /= 3;
    while(d % 5 == 0) five++, d /= 5;

    double sum = 0;
    FOR(i, two, 201){
      FOR(j, three, 101){
        FOR(k, five, 101){
          sum += dp[cur][i][j][k];
        }
      }
    }
    rep(i, N){
      sum /= 6.0;
    }
    cout << setprecision(20);
    p(sum * (d==1));

    return 0;
}

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～