AtCoder Grand Contest 050 (Good Bye rng_58 Day 1) C問題 - Block Game

Source

AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)
問題文

問題概要

省略

解法

省略

cLayversion 20201228-1)のコード

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

#define MD 998244353
int N;
char S[1d6+2];

int bt[1d6+2], bl[23], br[23], bef[1d6+1];
Modint dp[23][1d6+1], dps[23][1d6+1];

{
  int i, j, k, nk, x, y;
  Modint res;
  rd(S@N);

  rep(i,2,1d6+2) bt[i] = bt[(i+1)/2] + 1;
  rep(i,23) bl[i] = int_inf, br[i] = -int_inf;
  rep(i,1d6+2) bl[bt[i]] <?= i, br[bt[i]] >?= i;

  rep(i,1,N){
    bef[i] = bef[i-1];
    if(S[i-1] == 'B') bef[i] = i-1;
  }

  rep(i,N){
    if(S[i] == 'B' || S[i] == '?') dp[22][i] = 1;
    if(S[i] == 'B') break;
  }
  rep(i,N){
    if(S[i] == 'B' || S[i] == '?'){
      rep(j,1,23) rep(k,1,23){
        x = max(bef[i], i - br[j]);
        y = i - bl[j];
        if(x > y) continue;
        nk = min(j, k-1);
        dp[nk][i] += dps[k][y+1] - dps[k][x];
      }
    }
    rep(k,1,23) dps[k][i+1] = dps[k][i] + dp[k][i];
  }

  res = 1;
  rep(i,N) if(S[i] == '?') res *= 2;
  rrep(i,N){
    rep(j,1,23) res -= dp[j][i];
    if(S[i]=='B') break;
  }

  rep(i,N) if(S[i] == 'B') break;
  if(i==N) res -= 1;

  wt(res);
}

Current time: 2021年09月28日23時53分44秒
Last modified: 2020年12月28日21時11分31秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC050 AGC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン: