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

唯物是真 @Scaled_Wurm

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

TopCoder SRM 583 Div 2 ○○- 1160->1254

28th, +3/-1 challenge
青くなれたのでしばらく休憩

250: SwappingDigits

与えられた数値のある2つの桁を入れ替えたときに最小になる数値を答える。
計算量に余裕があるので総当りで解いた。
longに収まりきらなかったのでBigIntegerを利用

import java.math.BigInteger;

public class SwappingDigits {

	public String minNumber(String num) {
		int L = num.length();
		BigInteger cand = new BigInteger(num);
		for(int i = 0; i < L; i++) {
			for(int j = i + 1; j < L ; j++) {
				if((i == 0) && (num.charAt(j) == '0')) {
					continue;
				}
				char temp[] = num.toCharArray();
				char swap = temp[i];
				temp[i] = temp[j];
				temp[j] = swap;

				cand = cand.min(new BigInteger(String.valueOf(temp)));
			}
		}
		return cand.toString();
	}

}

550: IDNumberVerification

IDが条件を満たしているか調べる。

日付のチェックが一番めんどくさい。
年のチェック以外はJavaのCalendarクラスに投げて、例外が出るかどうかで判断した。

以下汚くなってしまったコード

import java.util.Calendar;
import java.util.HashSet;

public class IDNumberVerification {

	public String verify(String id, String[] regionCodes) {
		HashSet<String> region = new HashSet<String>();

		for(String s: regionCodes) {
			region.add(s);
		}

		String reg = id.substring(0, 6);
		if(!region.contains(reg)) {
			return "Invalid";
		}

		Calendar cal = Calendar.getInstance();
		cal.setLenient(false);
		int year = Integer.parseInt(id.substring(6, 10));
		int month = Integer.parseInt(id.substring(10, 12)) - 1;
		int date = Integer.parseInt(id.substring(12, 14));
		if((year < 1900) || (year > 2011)) {
			return "Invalid";
		}
		cal.set(year, month, date);
		try {
			for(int i = 0; i < 3; i++) {
				System.out.println(cal.get(i));
			}
		} catch(Exception e) {
			return "Invalid";
		}
		int mf = Integer.parseInt(id.substring(14, 17));
		if(mf == 0) {
			return "Invalid";
		}

		int sum = 0;
		String check = id.substring(17, 18);
		if(check.equals("X")) {
			sum = 10;
		} else {
			sum = Integer.parseInt(check);
		}
		for(int i = 0; i < 17; i++) {
			int m = Integer.parseInt(id.substring(i, i + 1));
			for(int j = 0; j < 17 - i; j++) {
				m = (m * 2) % 11;
			}
			sum = (sum + m) % 11;
		}

		boolean fail = true;
		System.out.println(sum + ", " + id);
		if(sum == 1) {
			fail = false;
		}

		if(fail) {
//		return null;
			return "Invalid";
		} else {
			if(mf % 2 == 0) {
				return "Female";
			} else {
				return "Male";
			}
		}
	}

}

900: GameOnABoard

与えられた盤面上を任意の始点から終点まで移動する時、最短経路が最長になる終点までの距離が最小になる始点を選んだ場合の始点から終点までの距離を答えるっぽい
ただし移動コストは0か1のどちらかで与えられる

蟻本を見ながらワーシャル・フロイド法だと終わりそうにないな~とか考えてましたが、終わってから冷静に考えると負の移動コストがないので、全部の点からダイクストラ法を実行すれば解けそうですね

-->