Hatena::Grouptopcoder

gnarl,TopCoder

2010-05-12

TCO10(Topcoder Open 2010) Algorithm Qual2

22:30

306位だった。Round1に行けるようだ。

問題の難易度的にはDiv2と同等だった。

500をかろうじて解いたところで時間切れという黄金パターン。1000に手をつけられるようになりたい……。

250 JingleRingle

JingleとRingleという二つのゲーム内通貨があって、売買する市場がある。取引の際、Jingleを売る側には税金がかかる。

税率と売買オファーがいくつか与えられるので、うまいこと取引したときの最大利益(Ringle)を求めよ。

Ringleは無制限に持ってるけどJingleは持ってない状態からスタート。

buyOffersから税金を引いて実際もらえる金額を計算しとく。

安いsellOfferから順にJingleを買って、高いbuyOfferの順に売る。利益が出なくなるポイントで終了。

import java.util.Arrays;

public class JingleRingle {

	public int profit(int[] buyOffers, int[] sellOffers, int tax) {
		for (int i = 0; i < buyOffers.length; i++)
			buyOffers[i] -= Math.floor((buyOffers[i] * tax) / 100.0);
		Arrays.sort(buyOffers);
		Arrays.sort(sellOffers);
		int bi = buyOffers.length - 1;
		int si = 0;
		int benefit = 0;
		while (0 <= bi && si < sellOffers.length
				&& buyOffers[bi] > sellOffers[si]) {
			benefit += buyOffers[bi] - sellOffers[si];
			bi--;
			si++;
		}
		return benefit;
	}
}

500 FuzzyLife

ふつうのライフゲーム。セルの初期状態が与えられるが、いくつかのセルは状態がはっきりしない('?'で表される)。

次ステップの生存セル数が最大になるように?の状態を決定せよ。

あるセルに隣接する状態が不明なセルは高々1個。

これ「nステップ後」とか「状態不明なセルはそこらじゅうにある」だとクソ難易度が高いんだけど、この条件ならかなり楽(と言いつつ実装がバグりまくって難儀したけど)。

'?'のセルを探して、そのセルが0の場合と1の場合それぞれについて次ステップのセル生存数を調べる。生存数が多かったほうを採用。

不明セルの影響を受けるのは対象セルを中心とした5*53*3のエリアだけ。

public class FuzzyLife {

	public int survivingCells(String[] grid) {
		final int W = grid[0].length();
		final int H = grid.length;

		final char[][] g = new char[H][];
		for (int y = 0; y < H; y++) {
			g[y] = grid[y].toCharArray();
		}

		for (int y = 0; y < H; y++) {
			for (int x = 0; x < W; x++) {
				if (g[y][x] == '?') {
					g[y][x] = determine(g, x, y);
				}
			}
		}

		int nextLive = 0;
		for (int y = -1; y < H + 1; y++) {
			for (int x = -1; x < W + 1; x++) {
				if (nextState(g, x, y) == '1')
					nextLive++;
			}
		}

		return nextLive;
	}

	char at(char[][] g, int x, int y) {
		if (x < 0 || g[0].length <= x)
			return '0';
		if (y < 0 || g.length <= y)
			return '0';
		return g[y][x];
	}

	private char determine(char[][] g, int x, int y) {
		g[y][x] = '0';
		int ifDead = calc9(g, x, y);
		g[y][x] = '1';
		int ifLive = calc9(g, x, y);

		return ifDead > ifLive ? '0' : '1';
	}

	private int calc9(char[][] g, int x, int y) {
		int liveNeighbors = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (nextState(g, x - 1 + i, y - 1 + j) == '1')
					liveNeighbors++;
			}
		}
		return liveNeighbors;
	}

	private char nextState(char[][] g, int x, int y) {
		final int live = count8(g, x, y);
		if (at(g, x, y) == '0' && live == 3)
			return '1';
		if (at(g, x, y) == '1' && (live == 2 || live == 3))
			return '1';
		return '0';
	}

	private int count8(char[][] g, int x, int y) {
		int live = 0;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++) {
				if (i == 1 && j == 1)
					continue;
				if (at(g, x - 1 + i, y - 1 + j) == '1')
					live++;
			}
		return live;
	}

}

1000 HandlesSpelling

目標文字列と、文字列の断片がいくつか与えられる。うまく組み合わせて目標文字列に近づければスコアが高くなるので最大スコアを求めよ。

問題読んだだけ。