人生初黄色記念
次参加してeasy hackとかで即落ちそう
最近競プロより優先してやるべきことが多いせいでだいぶ競プロから離れてる
考察力も落ちたと思うけど、それよりも実装力が落ちたのを強く実感する
前は絶対やらなかったようなバグをよく生んでる
今の感じだと行けたとして黄色が最終到達点になる気がしてる
前ほど競プロをがっつりやる時間が今後たぶんない
人生でここまで熱中できたものは麻雀とlolぐらいしかなかった😢
出来ればその2つより先に出会いたかった・・
解いた問題で使った知識を記憶に定着させるのを主な目的として記事を書いてて、それ自体は全く苦ではなかったんだけど、今時間的にキツイので今後はわからん
変色とかオンサイト参加とかがあったら記念に書くかもしれない
問題
m個のブロックがあり、それぞれのブロックに対して「n個の山のどれかに等確率で積む」という操作をする
操作終了後、ブロックが一番多く置かれている山が複数存在する確率を求めよ
1 <= n, m <= 50
解法
dp[i][j][k][L]: i番目の山まででj個のブロックを置き、ブロックの最大値がkで、k個のブロックが置かれている山がL個ある状態になる確率
Lを0〜50までとると遷移込みでO(n^2 m^3)になって間に合わないけど、L>=2は全部まとめられるのでO(n^2 m^2)で間に合う
遷移は普通にi番目の山に [0, m-j] 個置く場合それぞれを考えて、x個置くなら場合の数は (m-j)Cx 通りあるから〜みたいな感じで
class TieForMax { public: double pa[55][55]; double comb(int n, int r) { if (r<0 || r>n) return 0; if (r==0) return 1; if (pa[n][r]) return pa[n][r]; return pa[n][r] = (comb(n-1, r-1) + comb(n-1, r)); } double getProbability(int m, int n) { if (n==1 || m==1) return 0.0; double dp[55][55][55][3] = {}, p[55] = {}; p[0] = 1.0; reps(i,1,55) p[i] = p[i-1] / n; dp[0][0][0][0] = 1.0; rep(i,n) rep(j,m+1) rep(k,m+1) rep(l,3) if (dp[i][j][k][l]) rep(x,m-j+1) dp[i+1][j+x][max(k, x)][(x>k ? 1 : min(l+(x==k), 2))] += dp[i][j][k][l] * comb(m-j,x) * p[x]; double res = 0; reps(i,1,55) res += dp[n][m][i][2]; return res; } };
こういう多次元だけど発想はシンプルなdpはtopcoder過去問埋めで結構やった気がする
https://community.topcoder.com/stat?c=problem_statement&pm=15237&rd=17396