Hatena::Grouptopcoder

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

 | 

2013-01-13

Single Round Match 566 Div 1 11:35 Single Round Match 566 Div 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 566 Div 1 - nodchipのTopCoder日記 Single Round Match 566 Div 1 - nodchipのTopCoder日記 のブックマークコメント

久々の参加です。リハビリのために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・・・
  • どうしたものやら
  • O((350 / 2)^3 log (10^18))なら間に合う?
  • 答えが合わない上にTLE・・・
  • 諦めよう
  • Opened
  • 以下はir5先生の回答を参考にPracticeで通したソースコードです
  • 巡回行列の積がO(N^2)になることに気づけませんでした
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

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

ゲスト



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