nodchipのTopCoder日記

■ Single Round Match 566 Div 1 11:35

久々の参加です。リハビリのために565の250を解いたら199ptsでした・・・。

Easy 250 PenguinSledding

• さっぱり解答が思いつかない
• 250ってこんなに難しかったっけ・・・
• とりあえず線分1本の時はsafe
• 長さ2の折れ線もsafe
• 三角形になっているのもsafeかな
• あとは・・・- 思いつかない・・・
• これだけだと数が全然足りてない
• 何が足りてないんだろう
• Sample 3を手動visualizeしてみる
• 一つのnodeから複数のnodeに枝があるのか
• こういう場合もsafeになりそう
• ならば
  • 一つのnodeから2つ以上のnodeにedgeが伸びている場合
  • edge1本の場合
  • 三角形の場合
  • edgeがない場合
• の4パターンを足せば良いっぽい
• Passed System Test

class PenguinSledding {
public:
	ll count2Plus(ll n) {
		return (1LL << n) - n - 1;
	}
	long long countDesigns(int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2) {
		int N = numCheckpoints;
		vector<set<int> > g(N);
		REP(i, checkpoint1.size()) {
			int a = checkpoint1[i] - 1;
			int b = checkpoint2[i] - 1;
			g[a].insert(b);
			g[b].insert(a);
		}

		long long result = 0;

		REP(i, N) {
			result += count2Plus(g[i].size());
		}

		// 頂点数3
		for (int i = 0; i < N; ++i) {
			for (int j = i + 1; j < N; ++j) {
				for (int k = j + 1; k < N; ++k) {
					if (g[i].count(j) && g[j].count(k) && g[k].count(i)) {
						++result;
					}
				}
			}
		}

		// 1本
		result += checkpoint1.size();

		// エッジなし
		++result;

		return result;
	}
}

• それにしても遅すぎorz

Middle 500 PenguinEmperor

• 毎日となりの街に移動するのか (<- 違う！)
• これ行列積だよねぇ・・・ (<- 合ってる)
• とりあえず書いてみる
• ライブラリペタペタ
• ・・・
• 答えが合わない上にTLE・・・
• あ・・・day日目にはday個離れた街に移動するのか
• ならばdayPassed / N日分行列積で残りは手動だ
• ・・・
• 答えが合わない上にTLE・・・
• どうしたものやら
• なら間に合う？
• 答えが合わない上にTLE・・・
• 諦めよう
• Opened
• 以下はir5先生の回答を参考にPracticeで通したソースコードです
• 巡回行列の積がになることに気づけませんでした

class PenguinEmperor {
public:
	vector<vector<ll> > mul(vector<vector<ll> >& a, vector<vector<ll> >& b) {
		int n = a.size();
		vector<vector<ll> > out(n, vector<ll>(n));
		REP(i, n) REP(j, n) {
			out[0][i] += a[0][j] * b[j][i] % MOD;
			out[0][i] %= MOD;
		}
		for (int i = 1; i < n; ++i) {
			REP(j, n) {
				out[i][j] = out[0][(i - j + n) % n];
			}
		}
		return out;
	}
	int countJourneys(int N, long long daysPassed) {
		vector<ll> loop(N);
		loop[0] = 1;
		for (int day = 1; day <= N; ++day) {
			vector<ll> next(N);
			REP(from, N) {
				next[(from - day + N) % N] += loop[from];
				next[(from - day + N) % N] %= MOD;
				if ((from - day + N) % N != (from + day) % N) {
					next[(from + day) % N] += loop[from];
					next[(from + day) % N] %= MOD;
				}
			}
			swap(next, loop);
		}

		vector<vector<ll> > m(N, vector<ll>(N));
		REP(i, N) REP(j, N) {
			m[i][j] = loop[(i + j) % N];
		}

		vector<vector<ll> > y = m;
		vector<vector<ll> > v(N, vector<ll>(N));
		REP(i, N) {
			v[i][i] = 1;
		}
		ll p = daysPassed / N;
		for (; p; y = mul(y, y), p >>= 1) if (p & 1) v = mul(v, y);

		vector<ll> way = v[0];

		for (int day = 1; day <= daysPassed % N; ++day) {
			vector<ll> next(N);
			REP(from, N) {
				next[(from - day + N) % N] += way[from];
				next[(from - day + N) % N] %= MOD;
				if ((from - day + N) % N != (from + day) % N) {
					next[(from + day) % N] += way[from];
					next[(from + day) % N] %= MOD;
				}
			}
			swap(next, way);
		}

		return way[0];
	}
}

Challenge Phase

• こうなりゃやけだ！
• 500最大ケースで絨毯爆撃だ
• -75
• orz

System Test

oxx 75.66 475位 2129->2013

• 教訓: 成績が悪いからといってやけを起こしてはならない

ツイートする