Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM483 DIV2 MEDIUM - MovieSeating (この記事を編集する[管理者用])

Source

TopCoder SRM483 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

とある映画館の座席は50行以下50列以下である.
どこが埋まっている場所でどこが埋まっていない場所か,与えられる.
隣り合ってなくても良いので,n人(区別する)が同じ行,または,同じ列に座る方法の数を求める問題.
nは8以下.

解法

組み合わせの数を計算するだけ.
nが1の時に注意.

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

class MovieSeating {
public:
long long getSeatings(int f, vector <string> mp) {
  ll i,j,k,x,y,add;
  ll res=0;

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

  rep(i,x){
    k=0;
    rep(j,y) if(mp[i][j]=='.') k++;
    add = 1;
    rep(j,f) add *= k--;
    res += add;
  }

  rep(i,y){
    k=0;
    rep(j,x) if(mp[j][i]=='.') k++;
    add = 1;
    rep(j,f) add *= k--;
    res += add;
  }

  if(f==1) res /= 2;

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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