Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Japan 2011 決勝 C問題 - ワイルドカード (この記事を編集する[管理者用])

Source

Google Code Jam Japan 2011 決勝 C問題

問題概要

問題分が日本語なので略.

解法

DPする.
dp[a][b]は1つ目の文字列のa文字目以降にマッチして,2つ目の文字列のb文字目以降にマッチしない,題意を満たす正規表現とすればいい.
最初や最後に*を使わないパターンにもうまく対応させる.

C++によるスパゲッティなソースコード
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int is_same(char a[], char b[], int len){
  int i;
  rep(i,len) if(a[i]!=b[i]) return 0;
  return 1;
}

int as, bs;
char a[200], b[200];
string dp[2][100][100];
int is_caled[2][100][100];

int is_same_memo[60][60][60];

int is_small(string &a, string &b){
  int i, ast;

  if(a.size() < b.size()) return 1;
  if(a.size() > b.size()) return 0;

  ast = 0;
  rep(i,a.size()) if(a[i]=='*') ast++;
  rep(i,b.size()) if(b[i]=='*') ast--;
  if(ast > 0) return 0;
  if(ast < 0) return 1;

  if(a < b) return 1;
  return 0;
}

void solve(int fg,int A, int B){
  int i,j,k,skip;
  int st,ed,len,ok;
  string res = "176487165789165978265927865789265728965789263578265378926528", tmp;

  if(is_caled[fg][A][B]) return;
  is_caled[fg][A][B] = 1;

  REP(st,A+fg,as) REP(ed,st,as){
    len = ed - st + 1;

    ok = 0;
    REP(j,B,bs-len+1){
//      if(is_same(a+st, b+j, len)){
      if(is_same_memo[st][j][len]){
        ok = 1;
        break;
      }
    }

    if(!ok){
      tmp = "";
      if(st != A) tmp += '*';
      rep(i,len) tmp += a[st+i];
      if(ed != as-1) tmp += '*';
      if(is_small(tmp,res)) res = tmp;
    } else {
      tmp = "";
      if(st != A) tmp += '*';
      rep(i,len) tmp += a[st+i];

      skip = 0;
      if(ed==as-1){
        if(is_same_memo[st][bs-len][len] == 0) skip=1;
      }

      if(st==0 && ed == as-1) skip = 1;

      if(st==0 && j!=0) skip = 1;

      if(!skip){
        solve(1,ed+1,j+len);
        tmp += dp[1][ed+1][j+len];
      }

      if(skip==1 && st==0 && j!=0 && ed != as-1){
        tmp += '*';
      }

      if(is_small(tmp,res)) res = tmp;
    }
  }

  dp[fg][A][B] = res;
//  printf("%d %d %d : %s\n",fg,A,B,res.c_str());
}

int main(){
  int i,j,k,l,m,n;
  string res;
  int size, count=0;

  scanf("%d",&size);
  while(size--){
    fprintf(stderr,"size %d\n",size);
    
    printf("Case #%d: ",++count);
    
    scanf("%s%s",a,b);
    as = strlen(a);
    bs = strlen(b);

    rep(i,as) rep(j,bs) rep(k,51) is_same_memo[i][j][k] = is_same(a+i,b+j,k);

    rep(i,2) rep(j,100) rep(k,100) is_caled[i][j][k] = 0;

    solve(0,0,0);
    res = dp[0][0][0];
    
    printf("%s",res.c_str());

    puts("");
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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