Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-07-19[過去問]SRM476(DIV1)

リアルタイムで参加できなかったのでやってみた。

SRM476 第一問(250点)

| SRM476 第一問(250点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM476 第一問(250点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10797&rd=14186

  • 2^50はムリ。
  • 最大まで飼ってみて、最も多く餌を食いつぶしてる奴から消していくのはどうだろう(確証はないけど)
  • サンプル通った
  • Failed System Test

もっと確実な方法はないだろうか?

  • 飼うペットの数を固定し、その中でコストの小さいものから取っていく方法。
  • 50 * (50 + 50項目のソート)なので余裕で間に合う。
  • サンプル通った
  • Passed System Test
public class Badgers {
	public int feedMost(int[] hunger, int[] greed, int totalFood) {
		int num = hunger.length;
		int foods[] = new int[num];

		for (int n = 1 ; n <= num ; n++) {
			int need = 0;
			for (int x = 0 ; x < num ; x++) {
				foods[x] = hunger[x] + greed[x] * (n - 1);
			}
			java.util.Arrays.sort(foods);
			for (int y = 0 ; y < n ; y++) {
				need += foods[y];
			}
			if (need > totalFood) {
				return n - 1;
			}
		}
		return num;
	}
}

SRM476 第二問(550点)

| SRM476 第二問(550点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM476 第二問(550点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10806&rd=14186

方針が全く思いつきません


所感

参加してたら確実にDIV2に落ちてたな