SRM 463 250pt: RabbitNumbering

TopCoder

問題概要

ウサギがN(<50)匹いる。各ウサギに[1,A[i]]の範囲の番号を一意に割り振る。そのような割り振り方の総数をMODで求める問題。

考えたこと

  • (これは本番でも簡単に通せた)
  • 番号の小さいやつほど制約が強いので、番号の小さいやつから割り振っていく。
  • 重要なのは区間に関して包含関係が成り立つような順序が入れられること。

practiceで通ったコード。

計算量O(N*log N)。
ret *= max(maxNumber[i] - i, 0);って書いた方が綺麗だったけど、まあいいや。

#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;

const int64 MOD = 1000*1000*1000 + 7;

struct RabbitNumbering {

	int theCount(vector <int> maxNumber) {

		sort(maxNumber.begin(), maxNumber.end());

		int64 ret = 1;
		for(int i=0; i<(int)maxNumber.size(); i++){
			//もう番号が余ってない
			if(maxNumber[i] - i <= 0){
				return 0;
			}

			ret *= maxNumber[i] - i;
			ret %= MOD;
		}

		return (int) ret;
	}

};