SRM564に参加してみた！

Java Contest SRM

おそらく一番有名なオンライン競技プログラミングコンテストである、TopCoderのSRM(Single Round Match)に参加してみました。
SRMが僕が今まで参加してきたコンテストと違うのは、獲得点数が時間が経つほど減っていくことと、問題文が英語であることです。英語が苦手な僕は後者がかなりきつい。

前々から参加してみたいと思っていたのですが、メールチェックが怠惰なせいで開催を知らせるメールを見るのがいつも開催した後ていうねorz
参加したのはSRM564 - Round 1 Room59です。初参加なのでコンテストの仕様がよく分からず、すごい緊張しました。あと、昨日ちょっとプラクティスをやってみたところ、英語がよく分からなくて問題の細かい部分がよく分からなかったのでそれが不安でした。

SRMは普通のコンテストのような「コーディングフェイズ」、他の人のコードを見て間違いを見つけると点がもらえる「チャレンジフェイズ」、自分のプログラムが正しいかが判定される「テスティングフェイズ」から成ります。


■コーディングフェイズ（75分）■

250点問題 FauxPalindromes

単語の意味が分からない！今調べたところ、Fauxは「人造の」、Palindromeは「回文」らしいです。
問題は「AXA」のような回文文字列は"PALINDROME"、「AAAAXA」のように同じ文字が連続した場合にそれを一文字にすると回文になる文字列は"FAUX"、どちらでもなければ"NOT EVEN FAUX"と出力する問題。

これは普通に実装すればOK。
回文判定は文字列の反転を使えば一瞬なんですが、Javaの文字列反転関数が思いつかず、ごり押しでひっくり返しました。今調べるとStringBufferクラスを使えば良いみたい。使ったこと無い・・・。
一番時間がかかったのは英語の問題でした。今回の英語は簡単だったと思うのですが、次の文の解釈に迷いました。
・If word is a palindrome, return "PALINDROME" (quotes for clarity, returned value are case sensitive.)
case sensitiveっていうのは小文字じゃ駄目ってことなんだろうけど、quotes for clarityが分かりません。clarityは透明、明快という意味らしい。「明快にするために戻り値に"をつけろ」なのか「明快にするためにここでは"を付けている（戻り値にはいらないよ）」なのか・・・。結局、要らないだろうと付けなかったらいけました。

//import java.util.*;
public class FauxPalindromes {
	boolean isPalindrome(String word){
		String rev = "";
		int len = word.length();
		for(int i = 0; i < len; i++) rev += word.charAt((len - 1) - i);
		return word.equals(rev);
	}
	boolean isFauxPalindrome(String word){
		String shk = "";
		int len = word.length();
		char c = word.charAt(0);
		for(int i = 0; i < len; i++){
			char nc = word.charAt(i);
			if(c != nc){
				shk += c;
				c = nc;
			}
		}
		shk += c;
		return isPalindrome(shk);
	}
	public String classifyIt(String word) {
		if(isPalindrome(word)) return "PALINDROME";
		else if(isFauxPalindrome(word))  return "FAUX";
		else  return "NOT EVEN FAUX";
		
	}
// BEGIN CUT HERE
	public static void main(String[] args) {
		FauxPalindromes temp = new FauxPalindromes();
		String a = "XXXXYYYYYZZXXYYY";//"TOPCODEREDOOCPOT";//"XXXYTYYTTYX";//"AAAAANNAA";
		System.out.println(temp.classifyIt(a));
	}
// END CUT HERE
}

190.26 / 250

ちなみに、「// ... CUT HERE」のコメントは、TopCoderにコードを提出した際に自動でその部分をカットしてくれる便利なものです。

500点問題 AlternateColors

赤、緑、青のボールがそれぞれr、g、b個あり、それを出来るだけ赤、緑、青の順に並べていき、k番目のボールの色を答える問題。
始め英語を読み間違えて題意を勘違いしていて、赤赤..赤緑..緑青..青と並べてk番目を求めると思ってましたw

r、g、b、kはlongで10^12まであるので、単純にシミュレーションは無理。なので、min(r, g, b)を行い、色を一つずつ消していきます。Vectorでv = ["BLUE"、"RED"、"GREEN"]をつくっていき、ある色のボールがなくなったらその色をvから取り除きます。こうすると、3色あるうちにkが0になったらv[k % 3]、2色のうちならv[k % 2]、1色ならv[0]をreturnすれば答えが出ます。

・・・と思っていたらこれでは駄目でした。青のボールが無くなって赤と緑の2色になるとvの並び順が悪いのでk % 2 == 0のときに緑であるのに、v = ["RED", "GREEN"]となっているために"RED"が返されてしまいます。なので、このパターンのときは特殊処理をいれておけばOKです。

import java.util.Vector;

//import java.util.*;
public class AlternateColors {
	long min3(long a, long b, long c){
		return Math.min(a, Math.min(b, c));
	}
	public String getColor(long r, long g, long b, long k) {
		//String ans = "";
		int num = 3;
		Vector<String> v = new Vector<String>(3);
		v.add("BLUE");
		v.add("RED");
		v.add("GREEN");
		long t = min3(r,g,b);
		r -= t;
		g -= t;
		b -= t;
		if(k <= 3 * t){
			return v.elementAt((int)(k % 3));
		}
		k -= 3*t;
		if(r == 0){v.remove("RED"); num--;}
		if(g == 0){v.remove("GREEN"); num--;}
		if(b == 0){v.remove("BLUE"); num--;}
		if(num == 1) return v.elementAt(0);
		//num == 2
		long d1, d2;
		boolean bRev = false;
		if(b == 0){d1 = r; d2 = g;bRev = true;}
		else{
			d1 = b;
			d2 = g == 0? r : g;
		}
		t = Math.min(d1, d2);
		d1 -= t;
		d2 -= t;
		if(k <= 2 * t) 
			if(bRev) return v.elementAt((int)(k % 2) == 0? 1 : 0);
			else return v.elementAt((int)(k % 2));
		return d1 == 0? v.elementAt(1) : v.elementAt(0);
		
	}
}

2問目の最後の欠陥に気付かず、3問目の1050点問題は見れませんでした。残り時間僅かでsubmit。
202.04 / 500


■チャレンジフェイズ（15分）■

他の人のコードを見るのが得意という人を僕は今まで見たことがありません。僕ももちろんそうで、人のコードの欠陥なんかとても発見できませんでした。
あと自分のコードが見られているのが分かるのですが、これは心臓に悪い・・・。どうせここで間違いが見逃されてもテスティングフェイズで看破されるんですけどね。

■テスティングフェイズ（5分〜10分くらい？）■

僕の順位は20人中9位とかで、まあまあかなーとか思っていましたが、テスティングで思ったよりも周りの人が落ちていき、最終順位は3位でした。これは素直に嬉しい。

1位 701.79 (2問)
2位 399.91 (2問)
3位 392.3 (2問) mkiken
4位 274.76 (1問)
5位 250.36 (1問)

1位の人ぱねえ。


なかなか面白かったので、また機会があったら参加したいですねー。

Rating 1200 → 1287


お世話になったサイト
http://gulfweed.starlancer.org/d/index.php?itemid=10 （環境設定のお話）
http://d.hatena.ne.jp/tomerun/20080922/1222101340 （得点のお話）



追記 （2012/12/13）
701.79点の人が僕のtwitterをフォローしてくれてビックリ。
あとDiv2での総合順位は196 / 927 位でした。
次回からはDiv1でやるらしいです。ガクブル。