kmjp's blog

競技プログラミング参加記です

挿入DP の検索結果:

Codeforces #554 Div2 F. Neko Rules the Catniverse

…>1)][(j<<M)|(mask)]+=1; //take if(j<K) A.v[((j+1)<<M)|(1<<(M-1))|(mask>>1)][(j<<M)|(mask)]+=1+__builtin_popcount(mask); } } A=powmat(N,A,(K+1)<<M); ll ret=0; FOR(mask,1<<M) ret+=A.v[(K<<M)|mask][0]; cout<<ret%mo<<endl; } 解法 この挿入DPは思いつかないわ…。

CPSCO2019 Session3: F - Flexible Permutation

…は何通りか。 解法 挿入DPで解く。 dp(n,a,b) := 1~nの並び順を決めたとき、P[i]>iとなるiがa個、P[i]<iとなるiがb個ある並び順 とし、状態遷移を考える。1~nのPermutationのどこかに(n+1)を加えることを考えよう。 末尾に加えると、a,bは変化しない dp(n+1,a,b) += dp(n,a,b) P[i]>iである場所とswapすると、n+1>iだがP[i]<n+1なのでbが1個増える dp(n+1,a,b+1) += a*dp(…

diverta 2019 Programming Contest: F - Edge Ordering

…番の黒頂点… の順で挿入DPの要領で重さを確定させていくことを考えよう。状態を以下のtupleで表すとする。 (n,b,c,s) := n個目までの頂点の重さ順が確定したとき、黒頂点はb個含まれていて、その組み合わせはc通りであり、黒頂点の重みの総和はsである それぞれの頂点を追加するとき、状態は以下の通り遷移する。 白頂点を追加するとき、どこに追加してもよいのでその位置は(n+1)通り。よって(n.b.c.s)→(n+1,b,(n+1)c,(n+2)s)と状態遷移する。 s…

第5回 ドワンゴからの挑戦状 予選 : E - Cyclic GCDs

…を昇順にソートして、挿入DPすることを考える。 (0-originで)i番目のニワトリを輪に加えるとき、 既存の輪のどこかに加える場合、その組み合わせはi通り、よって美しさにはi倍寄与する 新規に輪を作る場合、和の美しさの定義より美しさにi倍寄与する こう考えると、多項式f(t) := (A[0]+0)*(A[1]+1)*...*(A[N-1]+N-1)を考えると、S(r)はf(t)のt^rの係数に相当することになる。 ここで、詳細はEditorialを参照して頂くとして、多…

yukicoder : No.645 Count Permutation

…追加される確率を適宜挿入DPの要領で考えるとH(p)はO(Np)で求めることができる。 Rが10^18なので、pは60程度まで数えればよい。 ll N,L,R; ll mo=1000000007; ll fact[101010]; ll dp[70]; void solve() { int i,j,k,l,r,x,y; string s; fact[0]=1; for(i=1;i<=100100;i++) fact[i]=fact[i-1]*i%mo; cin>>N>>L>>…

TopCoder SRM 694 Div2 Hard UpDownNess

SRM

…のを求めよ。 解法 挿入DPで解く。 大きい順に値をPに埋めていくことを考えよう。a個空きがある数列にaを埋める場合、左からb個目に数字を埋めると、その左には(b-1)個、右には(a-b)個aより小さい数字が入るので、あとの数字の埋め方はどうであってもP[i]<P[a]>P[j]となる(i,a,j)の組は(b-1)*(a-b)個増える。 あとは残り(a-1)個空きがある数列に(a-1)を埋めることを考えればよい。この考察から、以下の状態をDPで更新していけば良いことがわかる。…

天下一プログラマーコンテスト2015 本戦(オープン) : E - 天下一コップ

…和を求めよ。 解法 挿入DPで解く。 まず長方形を高さで降順にソートする。(1-originで)高い順にx番の長方形に対し、その上にy番(y<x)の高さまで水が注がれるケースの組み合わせ総数f(x,y)を考える。 そうすると解はである。 このf(x,y)がO(1)で求められれば、総和はO(N^2)で求められる。 O(N^2)では部分点にしかならないが、まずはf(x,y)を考えよう。x番の上にy番までの高さに水が注がれるには、y番未満の長方形は全部x番の左で、y番だけがx番の右…

yukicoder : No.93 ペガサス

…、X*Xの盤面を作る挿入DPで処理する。各列にはどこかの行に1個駒がある。 ここで、隣接する列において駒がある行の差が2の場合、不成立な隣接状態があると考える。 X行目まで処理した状態として、dp[X][不成立な列の対の数][(X-3,X-1)行目におかれた列は隣接しているか][(X-2,X)行目におかれた列は隣接しているか]を持ち、(X+1)行目の状態を更新する。X+1行目の置き方によって、以下のように状態が変化する。 (X-3,X-1)行目におかれた列が隣接している場合、…

TopCoder SRM 635 Div1 Hard ColourHolic

SRM

…])%=mo; } ll ret=0; FOR(i,402) { ll pat=(dp[0][0][i][0]+dp[0][0][i][1])%mo; ll t=0; for(x=i;x<=401;x++) (t+=dp2[x]*combi(n[0]+n[1]+1-i , x-i))%=mo; ret=(ret+pat*t)%mo; } return (int)ret; } } まとめ 挿入DPとか、基本的なアイデアは本番にも思いつけたものの本番中に最後まで到達できなかった。

興味深い問題: 2014/10-12

…g Nクイーンの変形というシンプルな問題ながら、挿入DPの状態遷移が面白い。 TopCoder SRM 642 Div1 Hard WheelofFortune - kmjp's blog 「ある状態になる確率の期待値」と「得られるスコアの期待値」と異なる2値をDPしていくのが面白かった。 Good Bye 2014: E. New Year Domino - kmjp's blog シンプルな問題設定でありながら、SegTree+ダブリングの使い分けという解法が面白かった。