TopCoder SRM 497

コード貼るならはてなでしょってことで、ひさびさにこちらに書きます。
5回目のTopCoder挑戦です。これまでの記録はこちら。 http://www.topcoder.com/tc?module=MemberProfile&cr=22907785&tab=alg

Div2 Easy: Filtering

public class Filtering {

	public int[] designFilter(int[] sizes, String outcome) {
		int minA = Integer.MAX_VALUE;
		int maxA = -1;
		int minR = Integer.MAX_VALUE;
		int maxR = -1;
		char[] chars = outcome.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			char c = chars[i];
			if (c == 'A') {
				minA = Math.min(minA, sizes[i]);
				maxA = Math.max(maxA, sizes[i]);
			} else {
				minR = Math.min(minR, sizes[i]);
				maxR = Math.max(maxA, sizes[i]);
			}
		}
		
		int[] ret = {minA, maxA};
		if (minR != Integer.MAX_VALUE && minA < minR) {
			ret = new int[0];
		} else if (maxR != -1 && maxR < maxA && minR < maxR ) {
			ret = new int[0];
		}
		return ret;
	}
	
}

Easyのわりに問題文長い。。理解に時間がかかった。
maxRの更新箇所でコピペの修正ミスがあり、Easyでは初のFailed。
そもそもRは最小値と最大値を取る必要なかった。

Div2 Medium: PermutationSignature

いい加減に解きたいMedium問題。

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

public class PermutationSignature {

	public int[] reconstruct(String signature) {
		int[] ret = new int[signature.length()+1];
		for (int i = 0; i < ret.length; i++) {
			ret[i] = i+1;
		}
		char[] chars = signature.toCharArray();
		List<Integer> res = new ArrayList<Integer>();
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(1);
		for (int i = 0; i < chars.length; i++) {
			if (chars[i] == 'I') {
				while (stack.size() != 0) {
					res.add(stack.pop());
				}
			}
			stack.push(ret[i+1]);
		}
		while (stack.size() != 0) res.add(stack.pop());
		for (int i = 0; i < ret.length; i++) {
			ret[i] = res.get(i).intValue();
		}
		return ret;
	}

}

境界条件ではまって提出が間に合わなかった。10分ほどオーバーして書き上げたのがこれ。
合ってると思うのですがいかに。

というわけで

初のEasy失敗でスコア0・・・。最悪の結果に終わり、レーティングは854まで落ちてしまいました。
次回から挽回です！

復習会

Div1をめざすには、やっぱり復習が大切ですよね。
今回はマリーチの開発メンバー三人で渋谷のルノアールに集まり、SRMの後に復習会をしました。Division Summaryから正解者のコードを開き、みんなで内容を理解したり、お互いのコードを見せ合ったり、と。
次回からは、SRMとは別の日の休日などに復習会をしようと思います。外の人も歓迎なので、またTwitterなどでお知らせいたします。