読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

TopCoder SRM 598 Div 2 ooo 1125->1156

topcoder 競技プログラミング

148th, +1/-2 challenge
Volatility 420->383

Hardがびっくりするほど簡単だったのだけど、なかなか気づけなかった

250: ErasingCharacters

手前から順番に2文字連続してる文字を消していくだけ

public class ErasingCharacters {
	public String simulate(String s) {
		StringBuffer buf = new StringBuffer(s);
		while(true) {
			boolean end = true;
			for(int i = 0; i < buf.length() - 1; i++) {
				if(buf.charAt(i) == buf.charAt(i + 1)) {
					buf.delete(i, i+2);
					end = false;
					break;
				}
			}
			if(end) {
				break;
			}
		}
		return buf.toString();
	}

}

500: BinPackingEasy

ビンパッキング
ある容量の入れ物と、ある大きさのアイテムの列があるときに何個の入れ物が必要か?

今回の条件だと1つの入れ物に最大でも2つまでしか入れられないので、貪欲にやっていけばできる

import java.util.Arrays;

public class BinPackingEasy {

	public int minBins(int[] item) {
		int[] bin = new int[50];
		Arrays.sort(item);

		for(int i = item.length - 1; i >= 0; i--) {
			for(int j = 0; j < 50; j++) {
				if(bin[j] + item[i] <= 300) {
					bin[j] += item[i];
					break;
				}
			}
		}
		int count = 0;

		for(int i = 0; i < 50; i++) {
			System.out.println(i + ", " + bin[i]);
			if(bin[i] == 0) {
				break;
			} else {
				count++;
			}
		}
		return count;
	}

}

1000: FoxAndFencingEasy

最初問題を勘違いしていて大幅にタイムロスした

プレイヤーが2人いて、それぞれ1次元の盤上に1つずつ駒が\(d\)離れておいてある
それぞれのプレイヤーが\(mov1, mov2\)の移動力で駒を左右に動かせるとき、どちらが勝利するかあるいは引き分けになるかを答える

最初の初手で到達できる\((mov1 >= d)\)場合はそちらの勝利
そうでない場合はどちらかの移動力が相手の2倍より大きければ勝てる\((mov2 > mov1 * 2)\)、\((mov1 > mov2 * 2)\)
それ以外の場合は引き分け

「2倍より大きい」を「2倍以上」にしている人がいたのでchallengeで落とした

ちなみに以下のソースコードの2つ目のif文は、なくても「2倍より大きい」の方でひっかかるので必要ない

public class FoxAndFencingEasy {

	public String WhoCanWin(int mov1, int mov2, int d) {
		if(mov1 >= d) {
			return "Ciel";
		}
		if(mov2 >= mov1 + d) {
			return "Liss";
		}
		if(mov1 > mov2 * 2) {
			return "Ciel";
		}
		if(mov2 > mov1 * 2) {
			return "Liss";
		}
		return "Draw";
	}

}
-->