Hatena::Grouptopcoder

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

 | 

2011-11-13

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

Easy 250 CountingSeries

  • 全部試せば・・・
  • upperBoundが大きいので無理
  • 範囲内の等差数列と等比数列の数を数えて、両方に所属する数を引くしかなさそう
  • 書いてみる
  • ・・・
  • 書けた
  • サンプルが合わない
  • "等比数列"で範囲外の物は除かないとけないのか (<-違う)
  • サンプル通った
  • Submit
    • Challenge Succeeded
  • 等差数列で範囲外のものを除くのを忘れていました

以下はPracticeで通したソースコードです

class CountingSeries {
public:
	long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
		ll arith =  a <= upperBound ? (upperBound - a + b) / b : 0;
		ll geo = 0;
		ll both = 0;
		while (c <= upperBound) {
			++geo;
			if ((c - a) % b == 0 && a <= c) {
				++both;
			}

			if (d == 1) {
				break;
			}

			c *= d;
		}

		return arith + geo - both;
	}
}

Midium 500 BricksN

  • DP
  • 多分 dp[h][w] だと思う
  • メモ探をしてみる
  • 多分 1x1xn のブロックを作る組み合わせは何パターンあるかが必要になるはずなので、予め計算しておく
  • 再帰関数の中では
    • 次にブロックを配置する連続する領域を決める
    • そこにブロックを配置するパターン数を数える
    • そこから上にブロックを配置するパターン数を数える
    • 同じ段の残りの部分に配置するパターン数を数える
  • 的な感じかな・・・
  • 書いてみる
  • 答えが合わない
  • 縦だけの場合と横だけの場合は合ってるっぽい
  • 残りのケースが微妙に小さい
  • ・・・
  • だめぽ・・・orz
  • Opened

以下はPracticeで通したコードです

const ll MOD = 1000000007;

ll coin[64];
ll dp[64][64];

class BricksN {
public:
	ll f(int h, int w) {
		if (h <= 0 || w <= 0) {
			return 1;
		}

		ll& r = dp[h][w];
		if (r) {
			return r;
		}

		for (int width = 1; width <= w; ++width) {
			r += coin[width] * f(h - 1, width) % MOD * f(h, w - width - 1) % MOD;
			r %= MOD;
		}

		r += f(h, w - 1);
		r %= MOD;

		return r;
	}
	int countStructures(int w, int h, int k) {
		CLEAR(coin);
		CLEAR(dp);
		coin[0] = 1;
		for (int i = 1; i <= 64; ++i) {
			for (int j = 1; j <= k; ++j) {
				if (i - j < 0) {
					continue;
				}
				coin[i] += coin[i - j];
				coin[i] %= MOD;
			}
		}

		return f(h, w);
	}
}

Hard 900 AlphabetPaths

  • うむむ?
  • 21*21*2^21って普通に考えると通らないよなぁ・・・
  • でもそれしか思いつかないのでとりあえず書いてみる
  • 書けた
  • サンプル通った
  • System Test通る気がしないけどとりあえず投げてみる
  • Failed Systemtest
  • Twitterを眺めていると両側探索というツイートが見えた
  • ちょっとやってみる
  • ・・・
  • MLEっぽいorz
  • どうやるんだろう・・・

Challenge Phase

  • 250で全数精査している人は・・・
  • さすがにいないか
  • 数年前だったら何人かやっていたのにレベルが上がったのだなぁ
  • ・・・
  • あ・・・250落とされた・・・
  • a<=upperBound入れてないからか
  • 他に入れていない人いないかなぁ
  • もう落とされているっぽいorz

System Test

Class NameMethod NameDifficultyCoding TimeStatusPoints
CountingSeriescountThemLevel One0:11:38.149Challenge Succeeded216.05
BricksNcountStructuresLevel Two0:43:06.261Opened0.00
AlphabetPathscountLevel Three0:15:24.856Failed System Test712.91

最近右肩下がりです・・・

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