Hatena::Grouptopcoder

TopCoder戦記

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

2009-09-29SRM427 DIV2

SRM427 DIV2 Level Three(1000pt.)

| 21:06

http://www.topcoder.com/stat?c=problem_statement&pm=10044&rd=13518

『アルファベットをK文字しか教えられない教師がいる。教師は生徒が与えられた単語(文字列)を数多く読めるよう、教えるべき文字を選ぶ。このとき生徒は最大で何単語読めるようになるか。』

アルファベットは26文字なので問題なくint型(32ビット)によってビットフラグ化できます。今回は各単語に使われている文字列をビットフラグ化することで、論理積のみで単語が読めるか否かを判別できるようにしました。また組み合わせの導出には神戸大学の教授でいらっしゃる谷崎久志さんのウェブサイトにある「組み合わせを求めるプログラムについて」をJavaへ移植させていただきました。

なお1度Submitに失敗したのですが、原因は教師が教える単語数が0の場合を想定していなかったこと。条件を飛ばさず読むようにしなければなりません。

// 419.55

public class Teaching {
	public int count(String[] words, int K) {
		if (K == 0) return 0;

		final int[] wordsBinary = asBinary(words);
		int readable = (1 << K) - 1;
		int result = 0;
		int max = 1 << 26;

		do {
			int count = 0;
			for (int wordBinary : wordsBinary) {
				if ((wordBinary & readable) == wordBinary) {
					++count;
				}
			}
			result = Math.max(count, result);
			readable = next(readable);
		} while (readable < max);
		return result;
	}

	private int[] asBinary(String[] words) {
		int[] wordsBinary = new int[words.length];
		for (int i = 0; i < words.length; ++i) {
			for (char c = 'z'; 'a' <= c; --c) {
				wordsBinary[i] = (wordsBinary[i] << 1)
						| (words[i].contains(Character.toString(c)) ? 1 : 0);
			}
		}
		return wordsBinary;
	}

	// see http://ht.econ.kobe-u.ac.jp/~tanizaki/class/combinat/combinat.pdf
	private int next(int source) {
		int param1 = smallestBitOf(source);
		int param2 = param1 + source;
		int param3 = smallestBitOf(param2);
		int param4 = param3 / param1;
		int param5 = param4 >>> 1;
		int param6 = param5 - 1;
		return param6 + param2;
	}

	private int smallestBitOf(int source) {
		int result = 1;
		while (source % 2 == 0) {
			source >>>= 1;
			result <<= 1;
		}
		return result;
	}
	
}

IterableなJava版next_combination(ビットフラグ版)

| 21:47

以前実装したIterableなJava版next_permutationと同じように、C++のnext_combinationJavaのIterable<Long>に置き換えて実装したもの。以下のようなコードで簡単に利用することができます。ビットフラグにはlong型を利用したため、最大で62個の組み合わせまで対応できます。

for (long l : new Combination(5, 3)) {
	String binaryString = String.format("%5s", Long.toBinaryString(l)).replace(' ', '0');
	System.out.println(binaryString);
}
/* 
 * RESULT:
 *   00111
 *   01011
 *   01101
 *   01110
 *   10011
 *   10101
 *   10110
 *   11001
 *   11010
 *   11100
 */

アルゴリズムは谷崎久志さんのウェブサイトにある「組み合わせを求めるプログラムについて」をJavaへ移植したものです。わかりやすい資料を公開してくださいまして、ありがとうございます。

// 2つのinner classをコピーして使用すること。
import java.util.Iterator;

public class CombTest {
	// SAMPLE
	public static void main(String[] args) {
		for (long l : new Combination(62, 2)) {
			String binaryString = String.format("%62s", Long.toBinaryString(l)).replace(' ', '0');
			System.out.println(binaryString);
		}
	}

	private static class Combination implements Iterable<Long> {
		private final int max;
		private final int select;
		
		public Combination(int max, int select) {
			if (max < 1 || 62 < max) {
				throw new IllegalArgumentException();
			}
			this.max = max;
			this.select = select;
		}
		@Override
		public Iterator<Long> iterator() {
			return new CombinationIterator(max, select);
		}
	}

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

		public CombinationIterator(int max, int select) {
			this.value = (1L << select) - 1L;
			this.max = 1L << max;
		}

		@Override
		public boolean hasNext() {
			return value < max;
		}

		@Override
		public Long next() {
			long stock = value;
			value = next(value);
			return stock;
		}

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

		private long next(long source) {
			long param1 = smallestBitOf(source);
			long param2 = param1 + source;
			long param3 = smallestBitOf(param2);
			long param5 = (param3 / param1) >>> 1;
			return param5 - 1 + param2;
		}

		private long smallestBitOf(long source) {
			long result = 1L;
			while (source % 2 == 0) {
				source >>>= 1;
				result <<= 1;
			}
			return result;
		}
	}
}