Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2012-02-05

Single Round Match 531 12:23 Single Round Match 531  - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 531  - nodchipのTopCoder日記 Single Round Match 531  - nodchipのTopCoder日記 のブックマークコメント

Easy 300 NoRepeatPlaylist

  • DP\(^o^)/オワタ
  • とりあえず考えてみる
  • DPの形はdp[何曲目][それまでに聞いた曲の種類数]だと思う
  • 更新式が思いつかない
  • M曲間重複してはならない条件をどう表せばよいか分からない
  • orz
  • 以下はkusanoさんのブログを参考にPracticeで通したコードです
    • 新しい曲を聞く場合と既に聞いた曲のうちM曲前までを除いた曲を聞く場合分け
    • 過去M曲には重複した曲は存在しないため、聞ける曲はmax(j-M,0)曲になるとのことです
class NoRepeatPlaylist {
public:
	int numPlaylists(int N, int M, int P) {
		ll dp[128][128] = {{}};
		dp[0][0] = 1;
		for (int p = 1; p <= P; ++p) {
			for (int n = 1; n <= N; ++n) {
				dp[n][p] = (dp[n - 1][p - 1] * (N - n + 1) + dp[n][p - 1] * max(n - M, 0)) % 1000000007;
			}
		}

		int result = dp[N][P];
		return result;
	}
}

Middle 500 MonsterFarm

  • これは行列のN乗して数が振動しなければおkなのではないだろうか?
  • 500にしてはやけにstraightforward過ぎるような・・・
  • とりあえず書けた
  • Submit
    • Failed System Test
    • Σ(゚д゚lll)ガーン
  • TLによると数が1,000,000,007の倍数になる場合があるらしい
    • ひどい
  • doubleかmod 1,000,000,009の場合も考慮すると通るらしいのでやってみる
  • ついでにmodの計算ライブラリと行列計算ライブラリを書きなおしてみる
  • 1,000,000,009は対策されていた!
  • じゃあ1,000,000,021で
  • 以下はPracticeで通したコードです
typedef long long ll;
template<ll M> struct G {
	ll x;
	G() : x(0) { }
	G(ll x) : x(x % M) { }
	G& operator += (const G& rh) { x = (x + rh.x) % M; return *this; }
	G& operator -= (const G& rh) { x = (x + M - rh.x) % M; return *this; }
	G& operator *= (const G& rh) { x = (x * rh.x) % M; return *this; }
	G& operator /= (const G& rh) { return *this *= rh.pow(M - 2); }
	G operator + (const G& rh) const { return G(*this) += rh; }
	G operator - (const G& rh) const { return G(*this) -= rh; }
	G operator * (const G& rh) const { return G(*this) *= rh; }
	G operator / (const G& rh) const { return G(*this) /= rh; }
	bool operator == (const G& rh) const { return x == rh.x; }
	bool operator != (const G& rh) const { return x != rh.x; }
	G& operator ++ () { return *this += 1; }
	G pow(ll e) const {
		G y(*this), v(1);
		for (; e; y *= y, e >>= 1)
			if (e & 1)
				v *= y;
		return v;
	}
	G C(ll k) {
		G v = 1;
		for (ll i = 1; i <= k; ++i) {
			v *= *this - i + 1;
			v /= i;
		}
		return v;
	}
};

template<class T> struct Matrix;
template<class T> struct Array : public vector<T> {
	Array() { }
	Array(int N) : vector<T>(N) { }
	Array operator*(const Matrix<T>& rh) {
		int N = this->size();
		Array o(N);
		REP(c, N) REP(r, N) o[c] += (*this)[r] * rh.m[r][c];
		return o;
	}
	Array& operator *= (const Matrix<T>& rh) {
		return *this = *this * rh;
	}
};

template<class T> struct Matrix {
	vector<Array<T> > m;
	Matrix() { }
	Matrix(int N) : m(N, Array<T>(N)) { }
	Matrix& identify() {
		int N = m.size();
		REP(n, N) m[n][n] = 1;
		return *this;
	}
	Array<T>& operator [] (int i) { return m[i]; }
	// 行列aと行列bの積 要素の順番は[行][列]
	Matrix operator * (const Matrix& rh) const {
		assert(m.size() == rh.m.size());
		int N = m.size();
		Matrix o(N);
		REP(r, N) REP(c, N) {
			T& t = o.m[r][c];
			REP(k, N) t += m[r][k] * rh.m[k][c];
		}
		return o;
	}
	Matrix& operator *= (const Matrix& rh) { return *this = *this * rh; }
	Matrix pow(ll p) const {
		int N = m.size();
		Matrix y = *this;
		Matrix v = Matrix(N).identify();
		for (; p; y *= y, p >>= 1) if (p & 1) v *= y;
		return v;
	}
};

typedef G<1000000007> G0;
typedef G<1000000021> G1;

class MonsterFarm {
public:
	int numMonsters(vector <string> transforms) {
		int N = transforms.size();
		Matrix<G0> m0(N);
		Matrix<G1> m1(N);
		REP(r, N) {
			istringstream iss(transforms[r]);
			int c;
			while (iss >> c) {
				--c;
				++m0[r][c];
				++m1[r][c];
			}
		}

		Array<G1> a1(N);
		a1[0] = 1;
		Array<G1> a10 = a1 * m1.pow(100);
		Array<G1> a11 = a1 * m1.pow(150);
		if (accumulate(ALL(a10), G1(0)) != accumulate(ALL(a11), G1(0))) {
			return -1;
		}

		Array<G0> a0(N);
		a0[0] = 1;
		Array<G0> a00 = a0 * m0.pow(100);
		Array<G0> a01 = a0 * m0.pow(150);
		if (accumulate(ALL(a00), G0(0)) != accumulate(ALL(a01), G0(0))) {
			return -1;
		}

		int result = accumulate(ALL(a00), G0(0)).x;
		return result;
	}
}

Hard 1000 BuildingReorganization

  • 考えてもわかりませんでした

Challenge Phase

  • 500で50x50のMatrixが来た時にTLEで落ちる人を探す
  • そんな人いない
  • 一定以上の数になった時に処理を撃ち切っている人を見つけた
  • 急いで最大ケースを作りなおす
  • +1
  • 以上終わり

System Test

SubmissionsDefensesChallengesSystemPointRatings
CodersQnty / Points Qnty / Points Qnty / PointsTestTotal Old / New
nodchip1320.75 00.00 150.00-320.7550.00 18641826

1864->1826 どうにか致命傷は免れました

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20120205
 |