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

唯物是真 @Scaled_Wurm

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

TopCoder SRM 574 Div 2 ○○- 1050->1070

topcoder

久しぶりの参加。281th
500を部屋内で2番目に提出したのに、間違いに終了5分前ぐらいに気づいて泣く泣くresubmit。
challenge 2回成功、1回失敗。
何故か部屋内のレートが低かったせいか、私ともう一人以外の500が全部challengeで落とされてしまい、部屋内で一位だった(´・ω・`)

250

文字列cityMap中に現れるアルファベットの頻度を数えて、POIsの数に等しい回数登場したアルファベットをつなげて出力するだけ。

public class CityMap {

	public String getLegend(String[] cityMap, int[] POIs) {
		int[] count = new int[26];
		for(String str: cityMap) {
			for(char c: str.toCharArray()) {
				if(c != '.') {
					count[c - 'A'] += 1;
				}
			}
		}
		String result = "";
		for(int n: POIs) {
			for(int i = 0; i < 26; ++i) {
				if(count[i] == n) {
					result += (char)(i + 'A');
				}
			}
		}
		return result;
	}
}

500

文字列AをBに変形するとき、回転と末尾の削除のコストをそれぞれ1としたときの、最小のコストを答える。
BがAの先頭に来る時と、Bが回文の時に気をつけながら条件文を書く。

終了直前に、回転してない場合とした場合の最小をとらないで、前者の条件を満たしたらすぐにreturnしていたミスに気づいて再提出したorz

public class TheNumberGameDiv2 {

	public int minimumMoves(int A, int B) {
		String strA = Integer.toString(A);
		String strB = Integer.toString(B);
		StringBuffer sb = new StringBuffer(strB);
		boolean palindromic = sb.reverse().toString().equals(strB);

		int offset_h = strA.indexOf(strB);
		StringBuffer sb_A = new StringBuffer(strA);
		int offset_t = sb_A.reverse().toString().indexOf(strB);
		int L_A = strA.length();
		int L_B = strB.length();
		int cand_h = 10000000;
		if(offset_h != -1) {
			int cost_h = offset_h;
			int cost_t = L_A - (offset_h + L_B);
			int rotate = 0;
			if(offset_h > 0) {
				rotate = palindromic ? 1 : 2;
			}
			cand_h =  cost_h + cost_t + rotate;
		}
		int cand_t = 10000000;
		if(offset_t != -1) {
			int cost_h = offset_t;
			int cost_t = L_A - (offset_t + L_B);
			int rotate = 1;
			cand_t = cost_h + cost_t + rotate;
		}
		if(offset_h != -1 || offset_t != -1) {
			return Math.min(cand_t, cand_h);
		}
		return -1;
	}

}

1000

n角形(4 <= n <= 13)の頂点を、経路が必ず過去の経路と交差するように巡っていって、最終的に出発地点に戻るときの場合の数を答える。
ただし最初に回る何点かは入力で与えられ、これらは交差していなくても良い。

初期に回る点を固定して、残りの数で順列を作って、それらすべてに対して条件をみたすか調べるという方針を考えたけど、実装が間に合わず。
必ず交差するという条件から初期の点は3つ以上じゃないとダメなので、n=13のときでも10の階乗通りしか頂点の順列は存在しない。
10の階乗かける交差するかどうかの判定で間に合うと思ったんだけど、どうなんだろうなぁ……。

と思って上位陣のソースコードを見たら普通に再帰でやっていた

-->