AtCoder Regular Contest 108 E問題 - Random IS

Source

AtCoder Regular Contest 108
問題文

問題概要

省略

解法

省略

cLayversion 20201121-1)のコード

C++に変換後のコードはこちら

int N, A[2002];
int v[2002], ind[2002];
Modint dp[2002][2002];
fenwick<Modint> d1[2002], d2[2002];
fenwick<int> d[2002];
{
  int i, j, t;
  rd(N,A(N));
  arrInsert(0, N, A, 0);
  arrInsert(N, N, A, N);

  rep(i,N) d[i].malloc(N,1);
  rep(i,N) d1[i].malloc(N,1);
  rep(i,N) d2[i].malloc(N,1);

  rep(i,N) (v[i], ind[i]) = (A[i], i);
  sortA(N, v, ind);

  rep(len,1,N) rep(ii,N-len){
    (i, j) = (ind[ii], ind[ii+len]);
    if(i >= j || A[i] > A[j]) continue;
    t = d[i].range(i,j);
    if(t){
      dp[i][j] += d1[i].range(i,j);
      dp[i][j] += d2[j].range(i,j);
      dp[i][j] /= t;
      dp[i][j] += 1;
    }
    d[i].add(j, 1);
    d1[i].add(j, dp[i][j]);
    d2[j].add(i, dp[i][j]);
  }

  wt(dp[0][N-1]);
}

Current time: 2021年09月28日08時35分54秒
Last modified: 2020年11月22日17時04分37秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Regular_Contest ARC108 ARC_E
トップページに戻る

Logged in as: unknown user (not login)

ログイン: