Codeforces Global Round 4 F2問題 - Long Colorful Strip

Source

Codeforces Global Round 4 F2問題 (1500pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20190721-1)のコード

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

//no-unlocked
#define MD 998244353

int N, M;
int C[1d6];

int vis[1000][1000];
mint dp[1000][1000];

int gmn[500], gmx[500];

mint solve(int a, int b){
  int i, j, k, mn, mx, dame;
  mint lef, rig, mul;

  if(a > b) return 1;
  if(vis[a][b]) return dp[a][b];
  vis[a][b] = 1;

  j = int_inf;
  rep(i,a,b+1) j <?= C[i];
  mn = gmn[j];
  mx = gmx[j];

  lef = rig = 0;
  dame = mn;
  for(i=mn;i>=a;i--){
    dame <?= gmn[C[i]];
    if(i <= dame) lef += solve(a,i-1) * solve(i,mn-1);
  }
  dame = mx;
  for(i=mx;i<=b;i++){
    dame >?= gmx[C[i]];
    if(i >= dame) rig += solve(mx+1,i) * solve(i+1,b);
  }

  mul = 1;
  rep(i,mn,mx+1){
    if(C[i]==j) continue;
    k = i;
    while(C[k+1]!=j) k++;
    mul *= solve(i,k);
    i = k;
  }

  return dp[a][b] = lef * rig * mul;
}

{
  int i, j, k, mn, mx;
  mint res;
  rd(N,M,(C--)(M));
  
  k = 1;
  rep(i,1,M){
    if(C[i]==C[i-1]) continue;
    C[k++] = C[i];
  }
  M = k;

  if(M > 2N){
    wt(0);
    return 0;
  }

  rep(i,N) gmn[i] = M;
  rep(i,N) gmx[i] = -1;
  rep(i,M) gmn[C[i]] <?= i;
  rep(i,M) gmx[C[i]] >?= i;

  rep(k,N){
    rep(i,gmn[k]+1,gmx[k]) if(C[i] < k){
      wt(0);
      return 0;
    }
  }

  res = solve(0, M-1);
  wt(res);
}

Current time: 2022年05月18日08時49分11秒
Last modified: 2019年07月21日16時02分06秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces Codeforces_Global_Round_4
トップページに戻る

Logged in as: unknown user (not login)

ログイン: