Entries

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

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

コメント

[C72]

"ID" is a placeholder for the string representation of an "existing" glob ID なので 50 くらいまでにしかならないです
  • 2011-01-01 12:16
  • rng
  • URL
  • 編集

[C73]

なるほど.ちゃんと問題文読まずに自分でテストするとき通ったのでvalidな入力なんだと思ってました.
  • 2011-01-01 12:44
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

SRM211 DIV2 HARD - grafixGlobs (この記事を編集する[管理者用])

Source

TopCoder SRM211 DIV2 HARD (900pt)
Problem Statement

問題概要

集合の演算のうち以下の操作を実装してシミュレーションする問題.
最終的にあるIDに含まれる図形の種類と数を求める.
IDは非負整数で,図形は弧,円,多角形の3種類.
 操作1 最初の空のIDに1つの図形を追加する
 操作2 指定したIDの図形を全部消去する
 操作3 指定したID aの図形を,指定したID bに全部加えて,ID aを消去する
 操作4 指定したIDの図形を全部消去し,消去した図形を1つずつ,最初の空のIDに追加していく.
空とは図形が含まれていないもの.操作の数は50以下.

解法

やるだけ.
ID番号2^32を消去するとやると,オーバーフローして間違うかと思ってチャレンジしたけど,
2^32は整数じゃないとか言われるし,2^31-1をIDとして指定すると,ジャッジがNULLを返したのであなたのチャレンジは無効ですとか言われた.
実はあんまりオーバーフローは考えなくて良いらしい.
(2011-01-01 12:45追記) どうやらIDは存在する範囲を指定しないとinvalidな入力らしい.コメント参照.指摘ありがとうございます.

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

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

class grafixGlobs {
public:
vector <int> execute(vector <string> commands, int sel) {
  int i,j,k;
  int id, jd;
  int x,y,z;
  double f;
  vector <int> res;
  int now[2000][3] = {};
  char a[1000], b[1000], c[1000];

  rep(k,commands.size()){
    sscanf(commands[k].c_str(),"%s%s%s",a,b,c);
    if(a[0]=='m' && a[1]=='a'){
      rep(i,2000) if(now[i][0]+now[i][1]+now[i][2]==0) break;
      if(b[0]=='a') now[i][0]++;
      if(b[0]=='c') now[i][1]++;
      if(b[0]=='p') now[i][2]++;
    }
    if(a[0]=='d' && a[1]=='e'){
      f = atof(b); if(f>1000) continue;
      id = atoi(b);
      now[id][0]=now[id][1]=now[id][2]=0;
    }
    if(a[0]=='m' && a[1]=='e'){
      f = atof(b); if(f>1000) continue;
      f = atof(c); if(f>1000) continue;
      id = atoi(b);
      jd = atoi(c);
      rep(i,3) now[id][i]+=now[jd][i], now[jd][i]=0;
    }
    if(a[0]=='s' && a[1]=='p'){
      f = atof(b); if(f>1000) continue;
      id = atoi(b);
      x = now[id][0];  y = now[id][1];  z = now[id][2];
      now[id][0] = now[id][1] = now[id][2] = 0;
      rep(i,1000) if(now[i][0]+now[i][1]+now[i][2]==0){
        if(x){ now[i][0]++; x--; continue; }
        if(y){ now[i][1]++; y--; continue; }
        if(z){ now[i][2]++; z--; continue; }
      }
    }

//    rep(i,3) printf("%d : %d %d %d\n",i,now[i][0],now[i][1],now[i][2]); puts("");
  }

  if(now[sel][0]+now[sel][1]+now[sel][2]) rep(i,3) res.push_back(now[sel][i]);
  return res;
}

};

コメント

[C72]

"ID" is a placeholder for the string representation of an "existing" glob ID なので 50 くらいまでにしかならないです
  • 2011-01-01 12:16
  • rng
  • URL
  • 編集

[C73]

なるほど.ちゃんと問題文読まずに自分でテストするとき通ったのでvalidな入力なんだと思ってました.
  • 2011-01-01 12:44
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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