Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM497 DIV1 MEDIUM - CssRules (この記事を編集する[管理者用])

Source

TopCoder SRM497 DIV2 MEDIUM (550pt)
Problem Statement
SRM497 DIV1 自分の参加記録

問題概要

問題文に定められた形式のXHTMLが与えられる.
それぞれのタグに,colorの指定があるが,それを全部CSSでやりたいとき,最小で何個のルールを作れば良いかを求める問題.
タグの名前は,bとuとiのみ.
カラーの名前は,black, blue, gray, green, red, white, yellowの7種類のみ.
タグは,タグの名前と,ユニークな任意文字列IDと,指定したい色で,構成される.
CSSのルールは以下の2種類が利用可能.
 IDを指定して,それの色を指定する
 IDとタグの名前Nを指定して,そのIDの中にある全てのタグの名前がNであるタグの色を指定する
ルールは好きな順番で与えることができて,複数のルールが適応される場所は,最後に適応した色になる.
与えられるXHTMLは50*50文字以下.(タグの数に直すと100未満程度)

解法

構文解析+DP.
現在どのタグにどの色が割り当てられているかを状態にして,そこからどのタグにどの色を割り当てるかを全部試す.
状態数が8^3 (8 = 7色+未割り当て) で,どの色を割り当てるかも8^3で,合計の計算時間は タグ数*8^6 程度.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

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

int node;
int edge[200][200], es[200];
int type[200], color[200];

int node_gen(char in[]){
  int i,j,k,now,st,add;

  now = node++;
  es[now]=0;
  
  if(in[1]=='/'){
    type[now] = -1;
    return 4;
  }

  if(in[1]=='b') type[now] = 0;
  if(in[1]=='u') type[now] = 1;
  if(in[1]=='i') type[now] = 2;

  for(i=0;;i++) if(in[i]==':') break; i++;
  if(in[i]=='b' && in[i+1]=='l' && in[i+2]=='a') color[now]=0;
  if(in[i]=='b' && in[i+1]=='l' && in[i+2]=='u') color[now]=1;
  if(in[i]=='g' && in[i+1]=='r' && in[i+2]=='a') color[now]=2;
  if(in[i]=='g' && in[i+1]=='r' && in[i+2]=='e') color[now]=3;
  if(in[i]=='r' && in[i+1]=='e' && in[i+2]=='d') color[now]=4;
  if(in[i]=='w' && in[i+1]=='h' && in[i+2]=='i') color[now]=5;
  if(in[i]=='y' && in[i+1]=='e' && in[i+2]=='l') color[now]=6;

  for(i=0;;i++) if(in[i]=='>') break;
  st = i+1;
  for(;;){
    edge[now][es[now]++]=node;
    add = node_gen(in+st);
    st += add;
    if(add==4) break;
  }

  return st;
}

int dp[200][8][8][8];

int solve(int now, int ok1, int ok2, int ok3){
  int i,j,k,l;
  int res = 0, add, tmp;
  int col;

  if(dp[now][ok1][ok2][ok3]>=0) return dp[now][ok1][ok2][ok3];

  if(type[now]==-1) return res;
  if(type[now]==0 && ok1!=color[now]) res++;
  if(type[now]==1 && ok2!=color[now]) res++;
  if(type[now]==2 && ok3!=color[now]) res++;

  tmp = 10000000;
  rep(i,8) rep(j,8) rep(k,8){
    add = 0;
    if(i!=ok1) add++;
    if(j!=ok2) add++;
    if(k!=ok3) add++;

    rep(l,es[now]) add += solve(edge[now][l],i,j,k);
    if(tmp > add) tmp = add;
  }
  res += tmp;

  
  return dp[now][ok1][ok2][ok3] = res;
}

class CssRules {
public:
int getMinimalCssRuleCount(vector <string> xthml) {
  int i,j,k,l;
  int res = 0;
  string in_baka;
  char in[10000];
  int st_node[1800], st_size;
  int len, st;

  rep(i,xthml.size()) in_baka += xthml[i];
  rep(i,in_baka.size()) in[i]=in_baka[i];
  len = in_baka.size();
  
  node = 0; st = 0; st_size=0;
  while(st<len){
    st_node[st_size++] = node;
    st += node_gen(in+st);
  }

  rep(i,node) rep(j,8) rep(k,8) rep(l,8) dp[i][j][k][l]=-1;
  rep(i,st_size) res += solve(st_node[i],7,7,7);

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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