Hatena::Grouptopcoder

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

 | 

2010-07-18

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

Easy 250 Badgers

  • Badgerという動物がいるらしいが、辞書をひく時間がもったいない
  • Badgerは非実在ペットということにしておこう
  • 考えてみる
  • 全部シミュレーションすると2^50になるから無理っぽい
  • どうしよう
  • 何匹飼うかを決め打ちしてしまえば、コストの低い方から貪欲に取ればよいか
  • 外側で何匹飼うかのループを回して内側でコスト低いやつをとればおk
  • 書けた
  • submit

結果: Failed System Test

  • "<N"と"<=N"を間違ったorz</li>

以下はPracticeを通した回答です

class Badgers {
public:
	int feedMost(vector <int> hunger, vector <int> greed, int totalFood) {
		const int N = hunger.size();
		int result = 0;
		for (int answer = 1; answer <= N; ++answer) {
			vector<int> costs;
			REP(i, N) {
				costs.push_back(hunger[i] + greed[i] * (answer - 1));
			}

			sort(ALL(costs));

			const int cost = accumulate(costs.begin(), costs.begin() + answer, 0);
			if (cost <= totalFood) {
				result = answer;
			}
		}

		return result;
	}
}

Middle 550 FriendTour

  • N=36!?
  • TSPのDPかけないじゃんorz
  • そもそも最適にたどるところの戦略が思いつかないorz

Hard 1000 SpaceshipEvacuation

  • ううむ
  • とりあえずホワイトボードにグラフを書き出してみる
  • なんだろうなぁ
  • 最小全域有向木を作ればいいのかなぁ
  • 乗り物が残っていたらコスト0、残ってなかったらコスト1かな?
  • とりあえず書いてみた
  • 答えが全然違っったorz

Challenge Phase

  • 250で愚直にシミュレーションしている人を狙っていこう
  • いなかった
  • もう時間がない
  • 部屋の中で1個だけ出ている500はなんかTLEしそう
  • 撃墜ケース間に合わないorz

System Test

x x x 0 pts 1921->1762

まとめ

3回連続の0完で一気にレーティングが落ちてしまいました。元に戻せるよう頑張ります。

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