SRM div2 500

一応自分が書いたコード

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

class MovieSeating {
private:
  long long permutation(int n, int r);
public:
  long long getSeatings(int numFriends, vector  hall) {
    int height = hall.size();
    int width = hall[0].length();
    long long sum = 0; //return
    //hall[0][j] , hall[1][j]
    for(int i = 0; i < height; i++) {
      int cnt = 0;
      for(int j = 0; j < width; j++) {
	if(hall[i][j] == '.') {
	  cnt++;
	}
      }
	sum += permutation(cnt, numFriends);
    }
    //hall[j][0], hall[j][1]
    for(int i = 0; i < width; i++) {
      int cnt = 0;
      for(int j = 0; j < height; j++) {
	if(hall[j][i] == '.') {
	  cnt++;
	}
      }
      sum += permutation(cnt, numFriends);
    }
    return sum;
  }

long long MovieSeating::permutation(int n, int r) {
  long long ans = 1;
  if(n < r) return 0;  //eg.)3P5 = 0
  for(int i = n; i > n-r; i--) {
    ans *= i;
  }
  return ans;
}

これでもいいけど、最適化するなら、メモ化して、1~max(width, height)を求めちゃうのもいいかもしれない．

//以下、めんどくさいので、擬似コード
long long dp[max(width, height)]
for[0, sizeof dp)
  dp[i] = permutation(i, numFriends); //メモ化