Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM498 DIV1 MEDIUM (450pt)
Problem Statement
SRM498 DIV1 自分の参加記録

問題概要

200*200以下の盤面の書くセルに,それぞれ違う色の石が1個ずつ置かれている.
50セル以下,指定されたセルがある.
セルAと指定されたセルとの距離が,全て,セルBと指定されたセルとの距離と等しければ,セルAの石とセルBの石を入れ替えることができる.
距離は,x座標の差とy座標の差の大きい方で定義される.(1-ノルム)
得られる盤面はいくらあるか,mod 1000000009で求める問題.

解法

AとBが入れ替え可能,BとCが入れ替え可能なら,AとCも入れ替え可能.
盤面は,いくつかの,それぞれ入れ替え可能なグループに分けることができる.
それぞれのグループ内では自由に入れ替えれるから,そのパターン数は,グループに属すセルの数の階乗.
それぞれのグループは,指定されたセルからの距離によって特徴付けられるので,それでグループ分けすれば良い.

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 M 1000000009
#define ll long long

int ab(int x){
  if(x<0) return -x;
  return x;
}

int dist[50][210][210];

class FoxStones {
public:
int getCount(int x, int y, vector <int> in_x, vector <int> in_y) {
  int i,j,k,n,s,ii,jj;
  map<vector<int>,int> mp;
  map<vector<int>,int>::iterator it;
  ll res=1;
  ll fact[100000];

  fact[0]=1; REP(i,1,100000) fact[i]=(fact[i-1]*i)%M;

  n = in_x.size();
  rep(i,n) in_x[i]--, in_y[i]--;
  rep(s,n) rep(i,x) rep(j,y){
    dist[s][i][j] = max(ab(in_x[s]-i),ab(in_y[s]-j));
  }

  rep(i,x) rep(j,y){
    vector<int> add;
    rep(k,n) add.push_back(dist[k][i][j]);
    mp[add]++;
  }

  for(it=mp.begin();it!=mp.end();it++)
    res = (res * fact[(*it).second])%M;

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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