Hatena::Grouptopcoder

TopCoder戦記

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

2009-08-31SRM433 DIV2

SRM433 DIV2 Level One(250pt.)

| 21:16

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

2つの配列A,Bが与えられたときに最小の「A[i]*B[i]の和」を求める。"大きな数値は小さな数値と掛け合わせれば良い"という考えを単純に実装するだけでOK。

// 244.28 pt.
import java.util.Arrays;

public class RoyalTreasurer {
	public int minimalArrangement(int[] A, int[] B) {
		Arrays.sort(A);
		Arrays.sort(B);
		int result = 0;
		for (int i = 0, n = A.length; i < n; ++i) {
			result += A[i] * B[n - i - 1];
		}
		return result;
	}
}

SRM433 DIV2 Level Two(500pt.)

| 21:16

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

与えられた複数の文字列を組み合わせて、特定の条件を満たす"MagicWord"がいくつ作れるかを調べる。

2秒の壁に阻まれてしまうため、メモ化を利用する必要がありました。Stringの連結がやたらと多いのが気になりますが、StringBuilderがCloneableでない以上単純な解決策はないでしょうTopSubmissionのように再帰ではなく順列を利用したアルゴリズムならばStringBuilderによってメモリ消費を抑えることができるようです。

// 215.32 pt.
import java.util.HashMap;
import java.util.Map;

public class MagicWords {
	private Map<Key, Integer> memo = new HashMap<Key, Integer>();

	public int count(String[] S, int K) {
		return count(S, "", K);
	}

	private int count(String[] s, String generated, int K) {
		Key key = new Key(s, generated);
		if(memo.containsKey(key)) {
			// メモ化による高速化
			return memo.get(key);
		}
		
		int count = 0;
		if (s.length == 1) {
			count = isMagicWord(generated + s[0], K) ? 1 : 0;
		} else {
			String[] ns = new String[s.length - 1];

			for (int i = 0; i < s.length; ++i) {
				for (int j = 0; j < ns.length; ++j) {
					ns[j] = i == j ? s[s.length - 1] : s[j];
				}
				count += count(ns, generated + s[i], K);
			}
		}
		memo.put(key, count);
		return count;
	}

	private boolean isMagicWord(String word, int K) {
		int count = 1;
		for (int i = 1; i < word.length(); ++i) {
			boolean isCyclic = true;
			for (int j = 0; isCyclic && j < word.length(); ++j) {
				isCyclic = word.charAt(j) == word.charAt((j + i) % word.length());
			}
			if (isCyclic) ++count;
		}
		return count == K;
	}
	
	class Key {
		final String[] s;
		final String g;
		Key(String[] s, String g) {
			this.s = s;
			this.g = g;
		}
		public int hashCode() {
			return s.length;
		}
		public boolean equals(Object o) {
			Key k = (Key)o;		// SRMだからできる荒技
			if (k.s.length == s.length) {
				for(int i = 0; i < s.length; ++i) {
					if(!s[i].equals(k.s[i])) return false;
				}
				return g.equals(k.g);
			}
			return false;
		}
	}
}

IterableなJava版next_permutation

| 22:00

C++ライブラリであるSTLに実装されているnext_permutationをJavaのIterable<int[]>に置き換えて実装したもの。以下のようなコードで簡単に利用することができます。

for(int[] permutation : new Permutation(3)) {
	System.out.println(Arrays.toString(permutation));
}
/* 出力結果:
	[0, 1, 2]
	[0, 2, 1]
	[1, 0, 2]
	[1, 2, 0]
	[2, 0, 1]
	[2, 1, 0] */

アルゴリズムはSRM433のTopSubmissionや、Googleによる検索結果を参考(ほぼ流用)にさせていただきました。先駆者の方々に感謝致します。

import java.util.Iterator;

/**
 * <p>順列を表すクラス。反復子によって順列を表すint型配列を生成・取得する。
 * @author eller
 */
// 若干まぎらわしいがPermutationListなどの命名がベターか。
public class Permutation implements Iterable<int[]> {
	private final int size;

	/**
	 * <p>順列を表すクラスのコンストラクタ。反復子が返す配列の要素数を指定する。
	 * @param size 順列の要素数(10程度が妥当な最大値)
	 * @throws IllegalArgumentException 引数(順列の要素数)が0以下の場合
	 */
	public Permutation(int size) {
		if (size <= 0) throw new IllegalArgumentException();
		this.size = size;
	}

	public Iterator<int[]> iterator() {
		return new Iter(size);
	}

	private class Iter implements Iterator<int[]> {
		private final int[] source;
		private boolean isFirst = true;

		private Iter(int size) {
			source = new int[size];
			for(int i = 0; i < size; ++i) {
				source[i] = i;
			}
		}

		/**
		 * <p>反復子がまだ順列を返しうるか調べる。
		 * 本メソッドは{@link Iter#next()}呼び出し前に必ず1回ずつ実行する必要がある。
		 * @return 順列が存在する場合はtrue
		 */
		public boolean hasNext() {
			if (isFirst) {
				isFirst = false;
				return true;
			}

			int n = source.length;
			for (int i = n - 1; i > 0; i--) {
				if (source[i - 1] < source[i]) {
					int j = n;
					while (source[i - 1] >= source[--j]);
					swap(source, i - 1, j);
					reverse(source, i, n);
					return true;
				}
			}
			reverse(source, 0, n);
			return false;
		}

		/**
		 * <p>次の順列を表すint型配列を返す。
		 * <p>このメソッドが返す参照は常に同じ配列に対する参照である。
		 * このため配列の要素を変更したり次回の{@link Iter#next()}呼び出し後も参照する場合は、
		 * クラスの呼び出し側が配列のクローンを生成して利用する必要がある。
		 * @return 順列を表すint型配列
		 */
		public int[] next() {
			return source;
		}

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

		private void swap(int[] is, int i, int j) {
			int t = is[i];
			is[i] = is[j];
			is[j] = t;
		}

		private void reverse(int[] is, int s, int t) {
			while (s < --t) swap(is, s++, t);
		}
	}
}