Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1335-72d38c22
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #17 C問題 - Balance (この記事を編集する[管理者用])

Source

Codeforces Beta Round #17 C問題
Problem description
Beta Round #17の自分の参加記録

問題概要

150文字以下のabcからなる初期値の文字列が与えられる.
 i+1番目の文字をi番目の文字と同じにする
 i番目の文字をi+1番目の文字と同じにする
という2種類の操作を際限なく繰り返すことができるとき,バランスされた文字列は何種類作れるかmod 51123987で求める問題.
バランスされた文字列とは,文字列に含まれている各文字の数の差の絶対値が1以下.

解法

要するに,例えば,入力文字列がabbcだったら,正規表現で書けば,a*b*b*c*にマッチするバランスされた文字列の数を求めれば良い.
状態を,
 正規表現の何処まで使ったか,次に来ることのできる文字種類,Aを何文字使ったか,Bを何文字使ったか,Cを何文字使ったか
としてDPする.

C言語のスパゲッティなコード

このコードは実際に本番でサブミットしたコード(のちょっと修正版)です.見にくいと思われます.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define LIM 60
#define M 51123987

int ab(int x){if(x<0) return -x; return x;}

int dp[8][LIM][LIM][LIM];
char in[160]; int len;

int main(){
  int i,j,k,l,m,n,r,res,sum,lim;
  int a,b,c;

  rep(m,8) rep(i,LIM) rep(j,LIM) rep(k,LIM) dp[m][i][j][k]=0;
  dp[7][0][0][0]=1;
  
  scanf("%d%s",&len,in);
  lim = (len+8)/3;

  rep(i,len) in[i]-='a';

  rep(l,len) if(!l || in[l]!=in[l-1]){
    if(in[l]==0){
      rep(m,8) if(m&1<<in[l]){
        rep(b,lim) rep(c,lim){
          sum = 0;
          REP(a,1,lim){
            sum = (sum+dp[m][a-1][b][c])%M;
            dp[7-(1<<in[l])][a][b][c] = (dp[7-(1<<in[l])][a][b][c]+sum)%M;
            dp[m-(1<<in[l])][a-1][b][c] = (dp[m-(1<<in[l])][a-1][b][c]+dp[m][a-1][b][c])%M;
            dp[m][a-1][b][c] = 0;
          }
        }
      }
    }
    if(in[l]==1){
      rep(m,8) if(m&1<<in[l]){
        rep(a,lim) rep(c,lim){
          sum = 0;
          REP(b,1,lim){
            sum = (sum+dp[m][a][b-1][c])%M;
            dp[7-(1<<in[l])][a][b][c] = (dp[7-(1<<in[l])][a][b][c]+sum)%M;
            dp[m-(1<<in[l])][a][b-1][c] = (dp[m-(1<<in[l])][a][b-1][c]+dp[m][a][b-1][c])%M;
            dp[m][a][b-1][c] = 0;
          }
        }
      }
    }
    if(in[l]==2){
      rep(m,8) if(m&1<<in[l]){
        rep(a,lim) rep(b,lim){
          sum = 0;
          REP(c,1,lim){
            sum = (sum+dp[m][a][b][c-1])%M;
            dp[7-(1<<in[l])][a][b][c] = (dp[7-(1<<in[l])][a][b][c]+sum)%M;
            dp[m-(1<<in[l])][a][b][c-1] = (dp[m-(1<<in[l])][a][b][c-1]+dp[m][a][b][c-1])%M;
            dp[m][a][b][c-1] = 0;
          }
        }
      }
    }
  }
  
  res=0;
  rep(m,8) rep(i,lim) rep(j,lim) rep(k,lim){
    if(i+j+k != len) continue;
    if(ab(i-j)>1 || ab(j-k)>1 || ab(k-i)>1) continue;
    res = (res+dp[m][i][j][k])%M;
  }
  printf("%d\n",res);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1335-72d38c22
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。