Hatena::Grouptopcoder

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

 | 

2009-10-18

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

Single Round Match 450 @ TopCoderCommentの参加記録です。

Easy 250 OrderedNim

変形Nimをプレイする。このNimではプレイヤーは一度に一つのパイルからいくつでも石を取ることができる。ただし複数あるパイルのうち、最も番号の若いパイルから歯科医師を取ることができない。AliceとBobがAlice先攻でプレイするとき、最適にプレイしたときにどちらが勝つか求めよ。

苦手なゲーム探索系が来てしまいました。オワタ

以前に多様な問題を解いたときには後ろから順番に解いていけば良かったような気がするのですが、細かいところが思い出せませんでした。結局寝た解答を提出してしまいましたorz

Middle 500 StrongEconomy

初期状態でn個の工場とk人の専門家いる。各ターンは、n×kの収入を得た後、price払って工場を建てる又は専門家を雇うという行動から成り立つ。工場の建設と専門家の雇用はお金がある限り何回でも行って良い。targetまでお金を貯めるまでに必要な最小ターン数を求めよ。

いつもなら即切っている問題なのですが、今回は500に手を付けると心に誓っていたため挑戦してみました。

入力の値が大きかったため貪欲アルゴリズムあたりだろうと当たりを付けて考え始めました。まず考えたのが工場を建てる又は専門家を雇うという部分です。貪欲的なアルゴリズムでは各ターン毎の収入を最も大きくしたほうが良いだろうと考え、n×kが最大になるように、値の小さいほうにインクリメントするという形にしました。

次に考えたのが入力の大きさです。for文で回すとTLEを食らう大きさだったため、複数回のループが必要となる場面は変数の割り算で代用し、なるべく時間がかからないようにしました。

最後は計算手順です。最終的に考えた計算手順は、「そのまま何もせずにtargetまで溜まるのに難ターンかかるか」「次に建設・雇用オプションがとれるまで何ターンかかるか」「何件建設・何人雇用するか」をループするという感じです。

提出前にランダムテストケースを食わせてみたところ、N×KがオーバーフローするケースでTLEしてしまったため、あわててC++からJavaに書き直しました。JavaTopCoderは久しぶりだったため、随所で手間取ってしまいました。

public class StrongEconomy {
	public long earn(long N, long K, long PRICE, long TARGET) {
		BigInteger n = BigInteger.valueOf(N);
		BigInteger k = BigInteger.valueOf(K);
		BigInteger price = BigInteger.valueOf(PRICE);
		BigInteger target = BigInteger.valueOf(TARGET);

		if (n.compareTo(k) < 0) {
			final BigInteger temp = n;
			n = k;
			k = temp;
		}

		BigInteger result = BigInteger.valueOf(0x7000000000000000L);
		BigInteger currentTurn = BigInteger.ZERO;
		BigInteger currentMoney = BigInteger.ZERO;
		while (currentTurn.compareTo(result) <= 0) {
			// そのまま溜まるのを待つ
			{
				final BigInteger restMoney = target.subtract(currentMoney);
				final BigInteger earn = n.multiply(k);
				final BigInteger restTurn = restMoney.add(earn).subtract(BigInteger.ONE).divide(earn);
				if (result.compareTo(currentTurn.add(restTurn)) >= 0) {
					result = currentTurn.add(restTurn);
				}
			}
			// どちらかが買えるまで待つ
			{
				final BigInteger restMoney = price.subtract(currentMoney);
				final BigInteger earn = n.multiply(k);
				final BigInteger spendTurn = restMoney.add(earn).subtract(BigInteger.ONE).divide(earn);
				currentTurn = currentTurn.add(spendTurn);
				currentMoney = currentMoney.add(spendTurn.multiply(earn));
			}

			final BigInteger build = currentMoney.divide(price);
			currentMoney = currentMoney.subtract(build.multiply(price));

			final BigInteger total = n.add(k).add(build);
			if (n.compareTo(total.add(BigInteger.ONE).divide(BigInteger.valueOf(2))) <= 0) {
				n = total.add(BigInteger.ONE).divide(BigInteger.valueOf(2));
			}
			k = total.subtract(n);
		}

		return result.longValue();
	}
}

Hard 1000 RowGame

覚えていません

撃墜フェーズ

500は自分がミスをしまくったため撃墜祭りになるだろうと予想し、絨毯爆撃を行いました。結果1成功5失敗と、惨敗してしまいました。

システムテスト

x o x -75

ゲーム系はちゃんと抑えておかないと駄目ですね・・・orz

総評

500が解けたので良しとしておきます・・・。

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