AtCoder Beginner Contest #122 D問題 - We Like AGC

Source

AtCoder Beginner Contest #122
問題文

問題概要

省略

解法

省略

cLay（version 20190714-1）のコード

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

int N;
mint dp[23], nx[23];

int dame[11][4] = {
  {0, 2, 1, -1},
  {2, 0, 1, -1},
  {0, 1, 2, -1},
  {0, 0, 2, 1},
  {0, 1, 2, 1},
  {0, 2, 2, 1},
  {0, 3, 2, 1},
  {0, 2, 0, 1},
  {0, 2, 1, 1},
  {0, 2, 2, 1},
  {0, 2, 3, 1}
};

{
  int i, j, k, x;
  mint res;
  AhoCorasick_Sum<int> aho;
  rd(N);

  aho.malloc(23, 4);
  rep(i,3) aho.addWord(dame[i], 3, 1);
  rep(i,3,11) aho.addWord(dame[i], 4, 1);
  aho.construct();

  k = aho.node;
  
  dp[0] = 1;
  rep(N){
    rep(i,k) nx[i] = 0;
    rep(i,k) rep(j,4){
      x = aho.next(i, j);
      if(aho.sum[x]) continue;
      nx[x] += dp[i];
    }
    rep(i,k) dp[i] = nx[i];
  }

  res = sum(dp(k));
  wt(res);
}

cLay（version 20190707-1）のコード

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

int N;
mint dp[5][5][5], nx[5][5][5];

int dame[5][4] = {
  {-1, 0, 2, 1}, 
  {-1, 2, 0, 1}, 
  {-1, 0, 1, 2}, 
  {0, -1, 2, 1}, 
  {0, 2, -1, 1}
};

{
  int i, j, k, s, m;
  mint res;
  dp[4][4][4] = 1;

  rd(N);
  rep(N){
    rep(i,5) rep(j,5) rep(k,5) nx[i][j][k] = 0;
    rep(i,5) rep(j,5) rep(k,5) rep(s,4){
      rep(m,5){
        if(dame[m][0]!=-1 && dame[m][0]!=i) continue;
        if(dame[m][1]!=-1 && dame[m][1]!=j) continue;
        if(dame[m][2]!=-1 && dame[m][2]!=k) continue;
        if(dame[m][3]!=-1 && dame[m][3]!=s) continue;
        break;
      }
      if(m==5) nx[j][k][s] += dp[i][j][k];
    }
    rep(i,5) rep(j,5) rep(k,5) dp[i][j][k] = nx[i][j][k];
  }

  res = 0;
  rep(i,5) rep(j,5) rep(k,5) res += dp[i][j][k];
  wt(res);
}

Current time: 2024年04月27日06時51分33秒
Last modified: 2019年07月14日04時11分29秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC122 ABC_D
トップページに戻る

Logged in as: unknown user (not login)