TopCoder SRM 420 div2

最近Registerに失敗しまくったので久々に参加。3週間ぶりくらい。

250点問題

赤黒カードの山があって、これを並び替える。i番目のカードは移動先のabove[i]枚目のカードの下に入れる。

public class DeckRearranging {
    public String rearrange(String deck, int[] above) {
    	final List<Character> l=new ArrayList<Character>();
		for(int i=0;i<deck.length();i++) {
			final char c=deck.charAt(i);
			final int a=above[i];
			l.add(a, c);
		}
		String s="";
		for(char c : l) s+=c;
        return s;
    }
}

まあ。

500点問題

日付を文字列で得て、一年のうちどれくらい過ぎたか返す。
SimpleDateFormatでパースして一発じゃｗｗｗ とか思ったら書式"M"が"January"をうまく解析してくれないなぜだ。
とか言ってたら仕事の話が入ったりしてげんなりしたのでこの問題はなし。

1000点問題

AからBまでかけた数を"D * 10^E"の形にプリティープリントして返す。ただしDが10桁以上のときは"上位5桁...下位5桁 * 10^E"
ふつうにやるとふつうにオーバーフローするのでどうするべっていう。
下位5桁とEは求まるんだけど上位五桁をどうしよう。ムリクソ浮動小数点を使ったりしてたら時間切れになった。

public class PrettyPrintingProduct {
    public String prettyPrint(int a, int b) {
    	long c=1;
    	long d=0;
    	
    	for(int n=a; n<=b; n++) {
    		c*=n;
    		while(c%10==0) {
    			c/=10;
    			d++;
    		}
    		if(10000000000L<=c) return prettyPrintLarge(a, b); //てきとうだなー
    	}
        return ""+c+" * 10^"+d;
    }
    private String prettyPrintLarge(int a,int b) {
    	long right=1;
    	double c=1.0;
    	final long x=100000;
    	int n2=0;
    	int n5=0;
    	for(int n=a; n<=b; n++) {
    		c*=n;
    		right*=n;
    		while(right%2==0) {
    			right/=2;
    			n2++;
    		}
    		while(right%5==0) {
    			right/=5;
    			n5++;
    		}
    		if(1000000000.0 < c) c/=100000.0;
    		right%=x;
    	}
    	final int d=Math.min(n2, n5);
    	while(n2<n5) { n5--; right*=5; right%=x; }
    	while(n5<n2) { n2--; right*=2; right%=x; }
    	final String ls=String.format("%1.0f", c);
    	final String rs=String.format("%05d", right);
    	return (ls.length()<=5?ls:ls.substring(0,5))+"..."+rs+" * 10^"+d;
    }
}

せっかくなのでコード書いてみた。こんなもんかなー。if(1000000000.0 < c) c/=100000.0; のあたりかなり適当、精度の見積もりができてない。
とりあえず問題付属のテストケースは動く。