2873 Apply a Cold Compress

一次元の文字列を受け取って、デコードし、二値の二次元画像を作成するという問題。
00,11は黒('X')、白の葉(' ')、10,01は枝（横に分割、縦に分割）に対応している。各葉の大きさは正方形でなければならず、また各枝の子は、10なら縦の長さ、01なら横の長さがともに等しくなるようにしなければならない（等しくなければ、子を拡大する）。
このとき、もっともサイズが小さくて済む画像を生成して出力するという問題。
日曜日の練習会で僕が実際に解いた（ただしJavaで）問題なのですが、何となくCで構造体バリバリに作ってみた。当然かなり短くはなったけど、やっぱり気持ち悪い。C言語の授業でこれが課題で出されたら泣きそうである。
つまらないけど、一応通ったコードを晒しておこう。
GCCで994byte（1000きったからやめた）。

typedef struct N{
  int t1,t2,w,h;
  struct N*l,*r;
}M;
i,j,w,h;
char s[999];M n;
gcd(a,b){
  return a%b?gcd(b,a%b):b;
}
char*p(M*n,char*s){
  i=*s++;
  j=*s++;
  n->t1=i-j;
  n->t2=j;
  if(n->t1==0){
    n->w=n->h=1;
    return s;
  }else{
    n->l=malloc(sizeof(M));
    n->r=malloc(sizeof(M));
    return(p(n->r,p(n->l,s)));
  }
}
q(M*n,int x,int y){
  if(n->t1){
    q(n->l,x,y);
    if(n->t2-'1')
      q(n->r,x+n->l->w,y);
    else q(n->r,x,y+n->l->h);
  }
  else for(i=0;i<n->h;i++)
    for(j=0;j<n->w;j++)
      s[(y+i)*w+x+j]=n->t2-'1'?'X':' ';
}
m(M*n,int a){
  n->w*=a;
  n->h*=a;
  if(n->t1)
    m(n->l,a),m(n->r,a);
}
c(M*n,int*x,int*y){
  if(n->t1){
    int w1,w2,h1,h2,g;
    c(n->l,&w1,&h1);
    c(n->r,&w2,&h2);
    if(n->t2-'1')
      g=gcd(h1,h2),m(n->l,h2/g),m(n->r,h1/g),n->w=n->l->w+n->r->w,n->h=n->l->h;
    else g=gcd(w1,w2),m(n->l,w2/g),m(n->r,w1/g),n->w=n->l->w,n->h=n->l->h+n->r->h;
    *x=n->w;
    *y=n->h;
  }else *x=n->w,*y=n->h;
}
main(){
  for(;gets(s);puts("")){
    p(&n,s);
    c(&n,&w,&h);
    ++w;
    q(&n,0,0);
    for(i=1;i<h+1;i++)
      s[i*w-1]=0;
    for(i=0;i<w+1;i++)
      putchar('-');
    puts("");
    for(i=0;i<h;i++)
      printf("|%s|\n",s+i*w);
    for(i=0;i<w+1;i++)
      putchar('-');
  }
}

関数名が一文字になってしまったので、簡単に機能の説明。

main

入力文字列を受け取り、rootに処理をさせ、出力する

p

parseの略。枝なら二つの子を生成し、子に続けてparseさせる。

q

printの略でpを使おうとしたら使われていたので次の文字。バッファにデコード結果を書き込む

m

multiplyの略。ノードの下全てをa倍する

c

calculateの略。最小のサイズになるように計算する