Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2009-08-23SRM435 DIV2

SRM435 DIV2 LEVEL One(250pt.)

| 05:48

http://www.topcoder.com/stat?c=problem_statement&pm=10294

スキー板とコースの摩擦を考慮し、ゴールまでに必要な時間を算出する問題。

単純な2重ループのみで解答可能でした。最大の摩擦を求める部分などをメソッドとして切り出すことも考えましたが、この程度の短さならば無理に分ける必要もないでしょう。

// 232.94 pt.
public class SkiFriction {
	public int bestPosition(String skiFriction, String pathFriction) {
		int sum = 0;
		for (int i = 0; i < pathFriction.length() - skiFriction.length(); ++i) {
			int maxFriction = 0;
			for (int j = 0; j < skiFriction.length(); ++j) {
				int friction = pathFriction.charAt(j + i) - '0' + skiFriction.charAt(j) - '0';
				maxFriction = Math.max(maxFriction, friction);
			}
			sum += maxFriction;
		}
		return sum;
	}
}

SRM435 DIV2 LEVEL Two(500pt.)

| 06:13

http://www.topcoder.com/stat?c=problem_statement&pm=10275

木構造のうち1ヶ所を破壊した後に、いくつの葉が残されているか調べる。木構造を表現することさえできればあとは簡単と思いきやシステムテストを通りません。

// 396.40 pt.
import java.util.*;

public class CellRemoval {
	public int cellsLeft(int[] parent, int deletedCell) {
		Cell[] cells = new Cell[parent.length];
		for (int i = 0; i < parent.length; ++i) {
			cells[i] = new Cell();
		}
		int rootNum = -1;
		for (int i = 0; i < parent.length; ++i) {
			int parentNum = parent[i];
			if (parentNum < 0) {
				rootNum = i;
			} else {
				cells[i].setParent(cells[parentNum]);
			}
		}
		cells[deletedCell].children.clear();
		return countLeafs(cells[rootNum]) - 1;	// deletedCellの分だけ減算
	}

	private int countLeafs(Cell cell) {
		int count = 0;
		for(Cell c : cell.children) {
			if (c.isLeaf()) {
				count++;
			} else {
				count += countLeafs(c);
			}
		}
		return count;
	}

	class Cell {
		final List<Cell> children = new ArrayList<Cell>();

		void setParent(Cell parent) {
			if (parent != null) {
				parent.children.add(this);
			}
		}

		boolean isLeaf() {
			return children.isEmpty();
		}
	}
}

mimanamimana2010/01/03 11:41countLeafs()に以下の1行が必要だと思うのですが。。
if(cell.isLeaf()) count++;

ellereller2010/01/03 12:07コメントありがとうございます。残念ながらそれを追加しても正常動作しないようですね。
この頃はシステムテストの実行方法がわかっていなかったので、テストケースが通ればよしとしていました。少しずつ見直していきたいと思います。