Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM562 DIV1 EASY - PastingPaintingDivOne (この記事を編集する[管理者用])

Source

TopCoder SRM562 DIV1 EASY (250pt)
Problem Statement

問題概要

50*50以下グリッドのクリップボードに絵がコピーされている.
絵は各セルR,B,Gのどれかの色か,透明のどちらか.
無限に大きいビットマップに,T回 (10^9以下) だけその絵をコピーする.
k回目のコピーでは,左上の座標が(k, k)になる場所にコピーする.
コピーした時,色があるセルは上書き,透明なセルは変化なし.
最初全部のセルが白のとき,最終状態でビットマップに,R, G, Bそれぞれの色は何セルずつあるかを求める問題.

解法

50回ぐらいコピーしたら後は増分は一定になる.
なので増分を求めて一気に足してあげる.
それぞれのピクセルについて,左上に見ていって,何ターン上書きされないかを求めても良い.

C++によるスパゲッティなソースコード
// #includeと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
char mp[1000][1000];

class PastingPaintingDivOne {
public:
vector<ll> countColors(vector <string> clip, int T) {
  int i, j, k, t;
  int x, y;
  vector<ll> res[200];

  x = clip.size();
  y = clip[0].size();

  rep(i,1000) rep(j,1000) mp[i][j] = '.';

  rep(t,200){
    rep(i,3) res[t].push_back(0LL);
    rep(i,x) rep(j,y) if(clip[i][j]!='.') mp[t+i][t+j] = clip[i][j];
    rep(i,t+x+10) rep(j,t+y+10){
      if(mp[i][j]=='R') res[t][0]++;
      if(mp[i][j]=='G') res[t][1]++;
      if(mp[i][j]=='B') res[t][2]++;
    }
  }

  if(T < 200) return res[T-1];

  rep(i,3) res[190][i] += (ll)(T-1-190) * (res[190][i] - res[189][i]);
  return res[190];
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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