Hatena::Grouptopcoder

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

 | 

2014-05-05

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

Easy 250 SplitStoneGame

  • でた・・・ゲーム木探索
  • これ1とそれ以外で分けちゃえばいいんだよね・・・?
  • Passed System Test
enum RESULT {
	WIN = 1,
	LOSE = 2
};
int dp[64][64];

class SplitStoneGame {
public:
	RESULT dfs(int numberOfOnes, int numberOfNonOnes) {
		assert(0 <= numberOfOnes);
		assert(0 <= numberOfNonOnes);

		if (dp[numberOfOnes][numberOfNonOnes]) {
			return (RESULT)dp[numberOfOnes][numberOfNonOnes];
		}

		if (numberOfNonOnes == 0) {
			return LOSE;
		}

		if (numberOfOnes + numberOfNonOnes <= 2) {
			return LOSE;
		}

		RESULT result = LOSE;

		for (int promoted = 0; promoted <= 2; ++promoted) {
			int unpromoted = 2 - promoted;
			if (numberOfOnes < promoted || numberOfNonOnes - 1 < unpromoted) {
				continue;
			}

			if (dfs(numberOfOnes - promoted, numberOfNonOnes - 1 + promoted) == LOSE) {
				result = WIN;
				break;
			}
		}

		return (RESULT)(dp[numberOfOnes][numberOfNonOnes] = result);
	}
	string winOrLose(vector <int> number) {
		int numberOfOnes = 0;
		int numberOfNonOnes = 0;
		for (int x : number) {
			if (x == 1) {
				++numberOfOnes;
			}
			else {
				++numberOfNonOnes;
			}
		}

		string result;
		if (dfs(numberOfOnes, numberOfNonOnes) == WIN) {
			result = "WIN";
		}
		else {
			result = "LOSE";
		}
		return result;
	}
}

Medium 600 GoodCompanyDivOne

  • 多分後ろからDP
  • 漸化式内ではフロー流すのかなぁ・・・
  • 手元でグラフを書いてみる
  • 多分1人につき2つのtaskというのがポイントのはず
  • 2つのtaskと1つのtaskを別のレイヤーにすれば制約を満たせる・・・?
  • レイヤーは
    • source
    • employee
    • task*task
    • task
    • sink
  • かな?
  • 書いてみる
  • サンプル通った
  • とりあえず出しておく
  • 念のため最大テストケースで確認
  • ・・・
  • TLEしたorz

Hard 1000 SimilarSequencesAnother

  • 全くわかりませんでした。

Challenge Phase

  • 250でメモし忘れている人を探してみる
  • ・・・
  • ってソースコード開けないんですけど
  • 再ログインしてみる
  • ・・・
  • できない・・・
  • なにこれ・・・
  • Arena再起動してみる
  • ログインできた
  • もういくつか落とされてる
  • とりあえず探す
  • いない・・・

System Test

oxx 352位

とりあえず1問解くことが出来ました。このまま低空飛行を続けられたらいいなぁと思います。

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