Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #74 DIV1 B問題/DIV2 D問題 - Widget Library (この記事を編集する[管理者用])

Source

Codeforces Beta Round #74 DIV1 B問題 (1000pt)
Codeforces Beta Round #74 DIV2 D問題 (2000pt)
Problem description

問題概要

厳密な仕様は問題文原文を参照.
横軸,縦軸がx軸,y軸に平行な長方形を作る.
以下の3タイプある.
 Widget: 縦,横のサイズが固定された長方形
 HBox: 箱.中身によってサイズが変わる.横に詰め込む.(問題文の図を参照)
 VBox: 箱.中身によってサイズが変わる.縦に詰め込む.(問題文の図を参照)
2種類のBoxには,2つのパラメータ (border, spacing) があって,詰め込む際の隙間のサイズが変わる.(問題文の図参照)
ただし,中身に何も入っていない箱は,パラメータの値に関わらず,サイズ0*0とする.
同じものが中に複数入っているかもしれない.
それぞれの長方形の横,縦の長さを全部求める問題.
入力は,長方形を作る,箱にものを入れる,パラメータを変える,の列からなり,最終的なサイズを求める.
パラメータの値は,設定しなければ,初期値は0.
ボックスの中に (結果的に) 自分自身が含まれることはないことが保証されている.

解法

各箱のサイズをメモ化再帰 (or トポロジカルソート+DP) で求める.

C++言語のスパゲッティなコード
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
using namespace std;

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

#define ll long long

int node;
int edge[120][120];
int type[120];

ll x[120], y[120];
int border[120], space[120];
int solved[120];

void solve(int now){
  int i,j,k;
  ll sum=0, mx=0, ele=0;

  if(solved[now]) return;
  solved[now] = 1;

  if(type[now] < 0) return;

  if(type[now]==0){
    rep(i,node) rep(j,edge[now][i]){
      ele++;
      solve(i);
      sum += x[i];
      if(mx < y[i]) mx = y[i];
    }

    x[now] = sum + (ele-1)*space[now] + border[now]*2;
    y[now] = mx + border[now]*2;
  }

  if(type[now]==1){
    rep(i,node) rep(j,edge[now][i]){
      ele++;
      solve(i);
      sum += y[i];
      if(mx < x[i]) mx = x[i];
    }

    x[now] = mx + border[now]*2;
    y[now] = sum + (ele-1)*space[now] + border[now]*2;
  }

  if(ele==0){
    x[now] = y[now] = 0;
    return;
  }
}

int main(){
  int i,j,k,l,m,n;
  map<string,int> mp;
  map<string,int>::iterator it;
  char in[1000];

  while(scanf("%d",&n)==1){
    node = 0;
    rep(i,120) rep(j,120) edge[i][j] = 0;
    rep(i,120) border[i] = space[i] = 0;

    mp.clear();

    while(n--){
      scanf("%s",in);
      if(in[0]=='W'){
        scanf("%s",in);
        for(i=0;;i++) if(in[i]=='(') break;
        sscanf(in+i,"(%d,%d)",&j,&k);

        x[node] = j; y[node] = k;
        type[node] = -1;
        in[i] = '\0';
        mp[(string)in] = node;

        node++;
        continue;
      }
      if(in[0]=='V'){
        scanf("%s",in);

        type[node] = 1;
        mp[(string)in] = node;
        node++;
        
        continue;
      }
      if(in[0]=='H'){
        scanf("%s",in);
        
        type[node] = 0;
        mp[(string)in] = node;
        node++;
        
        continue;
      }

      {
        string input = in;
        string name, op, val;

        for(i=0;;i++) if(input[i]=='.') break;
        name = input.substr(0,i);
        input = input.substr(i+1);

        for(i=0;;i++) if(input[i]=='(') break;
        op = input.substr(0,i);
        input = input.substr(i);

        val = input.substr(1,input.size()-2);

        if(op == "pack"){
          edge[mp[name]][mp[val]]++;
          continue;
        }
        if(op == "set_border"){
          border[mp[name]] = atoi(val.c_str());
          continue;
        }
        if(op == "set_spacing"){
          space[mp[name]] = atoi(val.c_str());
          continue;
        }
      }
    }

    rep(i,node) solved[i] = 0;
    rep(i,node) solve(i);

    for(it = mp.begin(); it!=mp.end(); it++){
      k = (*it).second;
      cout << (*it).first << " " << x[k] << " " << y[k] << endl;
    }
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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