AtCoder Grand Contest 037 B問題 - RGB Balls

Source

AtCoder Grand Contest 037
問題文

問題概要

省略

解法

省略

cLayversion 20190902-1)のコード

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

#define MD 998244353

int N;
char S[300001];

int Rs, Gs, Bs;
int up[1d5], md[1d5], dw[1d5];

mint dp[1d5], s[100001], nx[1d5];

{
  int i, j, k;
  mint res, tmp;
  
  rd(N,S);

  k = 0;
  rep(i,3N){
    if(S[i]=='R') up[Rs++] = i;
    if(S[i]=='G') md[Gs++] = i;
    if(S[i]=='B') dw[Bs++] = i;
    if(Rs > k && Gs > k && Bs > k){
      sortE(up[k], md[k], dw[k]);
      k++;
    }
  }

  res = 1;

  j = N-1;
  for(i=N-1;i>=0;i--){
    while(j>=0 && dw[j] > md[i]) j--;
    res *= i - j;
  }

  j = N-1;
  for(i=N-1;i>=0;i--){
    while(j>=0 && md[j] > up[i]) j--;
    res *= i - j;
  }

  rep(i,N) res *= i+1;
  
  wt(res);
}

Current time: 2021年09月24日18時42分27秒
Last modified: 2019年09月04日00時12分42秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC AGC_B
トップページに戻る

Logged in as: unknown user (not login)

ログイン: