2010年11月25日木曜日

TopCoder練習 SRM420 DIV2

250 問題文(要ログイン)
public class DeckRearranging {
 public String rearrange(String deck, int[] above) {
  String a = new String();
  for(int i = 0; i < deck.length(); i++) {
   a = a.substring(0, above[i]) + String.valueOf(deck.charAt(i)) + a.substring(above[i]);
  }
  return a;
 }
}
簡単。
500 問題文(要ログイン)
import java.text.ParsePosition;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.GregorianCalendar;
import java.util.Locale;

public class YearProgressbar {
 public double percentage(String currentDate) {
  SimpleDateFormat sdf = new SimpleDateFormat("MMM dd, yyyy HH:mm z", Locale.US);
  Date date = sdf.parse(currentDate + " EST", new ParsePosition(0));
  
  GregorianCalendar current = new GregorianCalendar();
  current.setTime(date);
  
  int year = current.get(GregorianCalendar.YEAR);
  GregorianCalendar start = new GregorianCalendar();
  String s = "January 01, " + Integer.toString(year) + " 00:00 EST";
  start.setTime(sdf.parse(s, new ParsePosition(0)));
  
  GregorianCalendar end = new GregorianCalendar();
  s = "January 01, " + Integer.toString(year + 1) + " 00:00 EST";
  end.setTime(sdf.parse(s, new ParsePosition(0)));
  
  return (double)(current.getTimeInMillis() - start.getTimeInMillis()) / (double)(end.getTimeInMillis() - start.getTimeInMillis()) * 100.0;
 }
}
今までで一番苦労しました。せっかくJavaを使っているんだからってCalendarクラスを使おうとした結果がこれだよ!

もう自分で実装したほうが早かったね・・・

ローカルではTestCaseが通るのに、TopCoder側では通らないという謎。
1時間以上悩んだ結果、原因は「夏時間」。
調べるうちにDateFormatクラスがあるから使ってやんよ、と思ったらこれもまた苦戦。
今度はローカルでSimpleDateFormatが動かない。なぜかTopCoder側で動く。
これは、Localeを指定しないと、月(Mayとか)を正しくとってこられないっぽい。デフォルトのままだと「5月」みたいに日本語表示しか読み取れなかったみたい。
そして、setTime(Date)した後は、setTimeZone(TimeZone)しても適用されていなくて、もうしょうがないから入力テキストにESTって記述してタイムゾーン指定してやったよ!!

他の人の解凍を見るとDateクラスの非推奨のメソッド使うともっと簡単にできたっぽい。もうやだ。

2010年11月20日土曜日

ドリームキャスト起動画面のジェネレータ作ってみた

ドリキャスの起動画面をFlashで再現してみた。

DC startup generator

生成されたURL(http://www.aaharu.com/dcdata/DC.swf?w=eJzzSM3JyddRCM8vyklRBAAfngRqなど)に飛べば、その文字列をいつでも再現できます。

Flashのソースコードも公開してあります。
Python(GAE)のコードの一部がこれ。
class GenerateHandler(webapp.RequestHandler):
    def post(self):
        form = self.request.get('words')
        if len(form) < 2:
            path = os.path.join(os.path.dirname(__file__), 'index.html')
            self.response.out.write(template.render(path, {'alert': "2文字未満は未対応です・・・"}))
        else:
            form = zlib.compress(form.encode('utf_8'))
            form = b64encode(form)
            self.redirect("../dcdata/DC.swf?w="+form)

GETでswfに文字列を渡しているのですが、流れとしては
HTMLのformで文字列をPOSTで送信→Pythonでzlib(gzip)圧縮→PythonでBase64エンコード→GETで渡す→swfでGET受信→ActionScriptでBase64をByteArrayにデコード→ByteArrayを解凍→文字列に挿入
て感じです。ちょっと違う?

TopCoder練習 SRM425 DIV2

250
問題文(要ログイン)
import java.util.Arrays;

public class InverseFactoring {
 public int getTheNumber(int[] factors) {
  if(factors.length == 1) return factors[0]*factors[0];
  Arrays.sort(factors);
  return factors[0]*factors[factors.length-1];
 }

}
問題読めたもん勝ち。最初のif文は別に書かなくてもいい。
とても簡単。

500
問題文
public class CrazyBot {
 private boolean point[][] = new boolean[30][30];
 private double _east;
 private double _west;
 private double _north;
 private double _south;
 private double result = 0.0;
 
 public double getProbability(int n, int east, int west, int south, int north) {
  for(int i = 0; i < 30; i++) {
   for(int j = 0; j < 30; j++) {
    point[i][j] = false;
   }
  }
  _east = (double)east;
  _west = (double)west;
  _north = (double)north;
  _south = (double)south;
  dfs(n, 0, 0, 1.0);
  return result;
 }
 
 private void dfs(int n, int x, int y, double p) {
  if(point[y+15][x+15]) {
   return;
  }
  if(n == 0) {
   result += p;
   return;
  }
  point[y+15][x+15] = true;
  dfs(n-1, x+1, y, p*_east/100.0);
  dfs(n-1, x-1, y, p*_west/100.0);
  dfs(n-1, x, y+1, p*_north/100.0);
  dfs(n-1, x, y-1, p*_south/100.0);
  point[y+15][x+15] = false;
 }
}
この問題は時間内に解けなくて、人の回答を参考にした。
問題文読んでDFS(深さ優先探索)使えばいいんだなーって思ったけどどう実装していいかわからなかった。明らかな実力不足。勉強になりました。

2010年11月17日水曜日

TopCoder練習 SRM 422 DIV2

250
問題文(要ログイン)
public class MultiNumber {
 public String check(int number) {
  if(number < 10) {
   return "NO";
  }
  String num = Integer.toString(number);
  //String.valuOf(number);
  for(int i = 1; i < num.length(); i++) {
   String a = num.substring(0, i);
   String b = num.substring(i);
   int n = 1, m = 1;
   for(int j = 0; j < a.length(); j++) {
    n *= Integer.parseInt(a.substring(j, j+1));
   }
   for(int j = 0; j < b.length(); j++) {
    m *= Integer.parseInt(b.substring(j, j+1));
   }
   if(n == m) {
    return "YES";
   }
  }
  return "NO";
 }
}
Javaでint→StringとString→intの変換する方法がわからなくて手間取った。 今気づいたけど、このプログラムちょっと無駄なことしてるね。

500
問題文
public class PrimeSoccer {
 public double getProbability(int skillOfTeamA, int skillOfTeamB) {
  double a = 0.0;
  double b = 0.0;
  //2
  a += ((double)skillOfTeamA/100.0) * ((double)skillOfTeamA/100.0) * 153.0 * Math.pow((double)(100 - skillOfTeamA)/100.0, 16.0);
  //3
  a += Math.pow((double)skillOfTeamA/100.0, 3.0) * 816.0 * Math.pow((double)(100 - skillOfTeamA)/100.0, 15.0);
  //5
  a += Math.pow((double)skillOfTeamA/100.0, 5.0) * 8568.0 * Math.pow((double)(100 - skillOfTeamA)/100.0, 13.0);
  //7
  a += Math.pow((double)skillOfTeamA/100.0, 7.0) * 31824.0 * Math.pow((double)(100 - skillOfTeamA)/100.0, 11.0);
  //11
  a += Math.pow((double)skillOfTeamA/100.0, 11.0) * 31824.0 * Math.pow((double)(100 - skillOfTeamA)/100.0, 7.0);
  //13
  a += Math.pow((double)skillOfTeamA/100.0, 13.0) * 8568.0 * Math.pow((double)(100 - skillOfTeamA)/100.0, 5.0);
  //17
  a += Math.pow((double)skillOfTeamA/100.0, 17.0) * 18.0 * (double)(100 - skillOfTeamA)/100.0;
  
  //2
  b += ((double)skillOfTeamB/100.0) * ((double)skillOfTeamB/100.0) * 153.0 * Math.pow((double)(100 - skillOfTeamB)/100.0, 16.0);
  //3
  b += Math.pow((double)skillOfTeamB/100.0, 3.0) * 816.0 * Math.pow((double)(100 - skillOfTeamB)/100.0, 15.0);
  //5
  b += Math.pow((double)skillOfTeamB/100.0, 5.0) * 8568.0 * Math.pow((double)(100 - skillOfTeamB)/100.0, 13.0);
  //7
  b += Math.pow((double)skillOfTeamB/100.0, 7.0) * 31824.0 * Math.pow((double)(100 - skillOfTeamB)/100.0, 11.0);
  //11
  b += Math.pow((double)skillOfTeamB/100.0, 11.0) * 31824.0 * Math.pow((double)(100 - skillOfTeamB)/100.0, 7.0);
  //13
  b += Math.pow((double)skillOfTeamB/100.0, 13.0) * 8568.0 * Math.pow((double)(100 - skillOfTeamB)/100.0, 5.0);
  //17
  b += Math.pow((double)skillOfTeamB/100.0, 17.0) * 18.0 * (double)(100 - skillOfTeamB)/100.0;
  double c = a*b;
  return a+b-c;
 }
}
ただの計算。プログラムより電卓でやったほうがいいんじゃね?ってレベル。
確率の計算です。組み合わせはGoogle電卓で出した。
18までの素数は7つしかないので結構無理やり解いてます。

2010年11月11日木曜日

TopCoderやってみた。

知り合いに誘われてTopCoderなるものに手を出してみました。
なぜかJAVAで参戦。Python使わせてください。

とりあえず、過去問で練習してます。
だめだめですけど、自分の解答を載せます。

TopCoder SRM 430 DIV 2
Problem 500 BitwiseEquations
問題文(アカウントがないと見られません)
public class BitwiseEquations {
 public long kthPlusOrSolution(int x, int k) {
  long a = 0, shift = 0;
  while(k > 0) {
   if((x & 1) == 0) {
    a |= ((long)(k & 1) << shift);
    k >>>= 1;
   }
   x >>>= 1;
   shift++;
  }
  return a;
 }
}
xを2進数で表示したときに0になる桁に、kの2進数の1桁目から入れていく感じ。
問題文からこのことを理解できれば解ける。結構時間かかった。

TopCoder SRM 427 DIV 2
Problem 250 LoveCalculator
問題文
import java.util.Arrays;

public class LoveCalculator {
 public String findBoy(String girl, String[] boys) {
  if(boys.length == 1) return boys[0];
  
  Arrays.sort(boys);
  
  int[] love = new int[boys.length];
  for(int i = 0; i < boys.length; i++) {
   int L = 0, O = 0, V = 0, E = 0;
   for(int j = 0; j < girl.length(); j++) {
    if(girl.charAt(j) == 'L') {
     L++;
    } else if(girl.charAt(j) == 'O') {
     O++;
    } else if(girl.charAt(j) == 'V') {
     V++;
    } else if(girl.charAt(j) == 'E') {
     E++;
    }
   }
   for(int j = 0; j < boys[i].length(); j++) {
    if(boys[i].charAt(j) == 'L') {
     L++;
    } else if(boys[i].charAt(j) == 'O') {
     O++;
    } else if(boys[i].charAt(j) == 'V') {
     V++;
    } else if(boys[i].charAt(j) == 'E') {
     E++;
    }
   }
   love[i] = ((L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E))%100;
  }
  int max = love[0], maxI = 0;
  for(int i = 1; i < love.length; i++) {
   if(love[i] > max) {
    maxI = i;
    max = love[i];
   }
  }
  return boys[maxI];
 }
}
そのまんま。コード汚い。