Hatena::Grouptopcoder

TopCoder戦記

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

2009-10-11SRM424 DIV2

SRM424 DIV2 Level Three(900pt.)

| 23:00

http://www.topcoder.com/stat?c=problem_statement&pm=10172&rd=13515

『一本道で相互に接続された街々がある。一定の法則にしたがい、道の選択に優先順位を与える。このときすべての街をつなぎ、かつ最も優先度の高いM本の道を選択せよ。』

900点問題の割に気をつけるべきポイントが多いように感じました。理解するためにはグラフ理論を学ぶ必要があるのでしょうか。例によってTopSubmissionはプリミティブ型を演算するだけのもので、解読に時間がかかりそうですがそれだけに得るものも多そうです。


一応コードも載せますが、低効率かつ読みにくいものになっています。これを保守しろといわれたら悩んでしまいますね……。

// TLE

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

public class BestRoads {
	public int[] numberOfRoads(String[] roads, int M) {
		if (M == 0) {
			return new int[roads.length];
		}
		final List<Road> list = new ArrayList<Road>();
		final int citiesNum = roads.length;
		for (int i = 0; i < roads.length; ++i) {
			for (int j = i + 1; j < roads.length; ++j) {
				if (reached(roads, i, j)) {
					final Road road = new Road(i, j);
					if (list.size() >= M - 1) {
						final int[] result;
						if ((result = connectedSet(list, road, M, citiesNum)) != null) {
							return result;
						}
					}
					list.add(road);
				}
			}
		}
		return new int[0];
	}

	private int[] connectedSet(List<Road> set, Road road, int M, int citiesNum) {
		ObjectCombination comb = new ObjectCombination(set, M - 1);
		for (List<Road> l : comb) {
			l.add(road);
			if (isConnected(l, citiesNum)) {
				return listToArr(l, citiesNum);
			}
		}
		return null;
	}

	private int[] listToArr(List<Road> l, int m) {
		final int[] result = new int[m];
		for (Road road : l) {
			++result[road.bigger];
			++result[road.smaller];
		}
		return result;
	}

	private boolean reached(String[] roads, int cityA, int cityB) {
		return roads[cityA].charAt(cityB) == 'Y';
	}

	private boolean isConnected(Collection<Road> roads, int citiesNum) {
		final boolean visited[] = new boolean[citiesNum];
		visited[0] = true;
		List<Road> next = null;
		do {
			if (next != null) {
				roads = next;
			}
			next = new ArrayList<Road>(roads.size());
			for (Road road : roads) {
				if (visited[road.smaller] || visited[road.bigger]) {
					visited[road.bigger] |= visited[road.smaller];
					visited[road.smaller] |= visited[road.bigger];
				} else {
					next.add(road);
				}
			}
		} while (!next.isEmpty() && !next.equals(roads));
		for (boolean b : visited) {
			if (!b)
				return false;
		}
		return true;
	}

	private static class Road {
		private final int smaller;
		private final int bigger;

		Road(int cityA, int cityB) {
			this.smaller = cityA;
			this.bigger = cityB;
		}
	}

	private static class ObjectCombination implements Iterable<List<Road>> {
		private final List<Road> c;
		private final int max;

		public ObjectCombination(List<Road> c, int max) {
			this.c = c;
			this.max = max;
		}

		public Iterator<List<Road>> iterator() {
			return new ObjectCombinationIterator(c, max);
		}
	}

	private static class ObjectCombinationIterator implements
			Iterator<List<Road>> {
		private final CombinationIterator childIterator;
		private final int max;
		private final List<Road> c;

		public ObjectCombinationIterator(List<Road> c, int max) {
			this.max = max;
			this.c = c;
			this.childIterator = new CombinationIterator(c.size(), max);
		}

		public boolean hasNext() {
			return childIterator.hasNext();
		}

		public List<Road> next() {
			final List<Road> l = new ArrayList<Road>(max);
			final BigInteger flag = childIterator.next();
			int count = 0;
			for (Iterator<Road> iter = c.iterator(); iter.hasNext();) {
				final Road road = iter.next();
				if (flag.testBit(count++)) {
					l.add(road);
				}
			}
			return l;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	private static class CombinationIterator implements Iterator<BigInteger> {
		private BigInteger value;
		private final BigInteger max;

		public CombinationIterator(int max, int select) {
			this.value = BigInteger.ONE.shiftLeft(select).subtract(BigInteger.ONE);
			this.max = BigInteger.ONE.shiftLeft(max);
			System.out.println(max + "," + select);
		}

		public boolean hasNext() {
			return value.compareTo(max) < 0;
		}

		public BigInteger next() {
			System.out.println(value.toString());
			BigInteger stock = value;
			value = next(value);
			return stock;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}

		private BigInteger next(BigInteger source) {
			BigInteger param1 = smallestBitOf(source);
			BigInteger param2 = param1.add(source);
			BigInteger param3 = smallestBitOf(param2);
			BigInteger param5 = param3.divide(param1).shiftRight(1);
			return param5.subtract(BigInteger.ONE).add(param2);
		}

		private BigInteger smallestBitOf(BigInteger source) {
			BigInteger result = BigInteger.ONE;
			if (source.equals(BigInteger.ZERO)) {
				throw new IllegalArgumentException();
			}

			for (int i = 0;; ++i) {
				if (source.testBit(i)) {
					return result.shiftLeft(i);
				}
			}
		}
	}
}