BottomCoder SRM 381 div2

TopCoder

SRM 381 div2

points result time
250 AC 5mぐらい？
500 AC 15mぐらい？
1000 WA 15mぐらい？

1000が本気でわからなかった。文字列構成ってああやってやるのね・・
案の定Vasylセット。

250

名前の強さの比較を次のルールで行う。

  • JOHNは無条件に最強。
  • Aを1, Bを2, …, Zを26として名前の各文字の合計が大きいほうが強い。
  • 上記の合計が同じ場合辞書順最小が最強。

与えられた文字列配列(||<=50, len<=50)を強い順に並べ替えよ。

3つのルールをこの順に実装してsortするだけでよい。最初、与えられた順が関係するのかとおもって順序配列を別につくってしまったがそんなことはなかった。JOHNは最強。

import java.util.Arrays;
import java.util.Comparator;

public class TheBestName {

	public String[] sort(String[] names) {
		Arrays.sort(names, new Comparator<String>(){
			public int compare(String x, String y)
			{
				if(x.equals("JOHN")){
					return -1;
				}
				if(y.equals("JOHN")){
					return 1;
				}
				
				int sa = 0;
				for(int i = 0;i < x.length();i++){
					sa += x.charAt(i) - 'A' + 1;
				}
				int sb = 0;
				for(int i = 0;i < y.length();i++){
					sb += y.charAt(i) - 'A' + 1;
				}
				
				if(sa != sb)return sb - sa;
				return x.compareTo(y);
			}
		});
		
		return names;
	}

}

500

キャンディの数がcandies(<=1000000)以上になるまで6面サイコロを振って、出た目の数だけキャンディをもらう。サイコロを振る回数の期待値を求めよ。

まずそれぞれのキャンディの個数になる確率を求める。これはp[0]=1, p[i]=(p[i-1]+p[i-2]+p[i-3]+p[i-4]+p[i-5]+p[i-6])/6でいける。確率p[i]でiにいるとき、サイコロを1回振って増える期待値はp[i]なので、E[i]=(E[i-1]+E[i-2]+E[i-3]+E[i-4]+E[i-5]+E[i-6])/6+(p[i-1]+p[i-2]+p[i-3]+p[i-4]+p[i-5]+p[i-6])/6. こうして求めたE[candies]〜E[candies+5]の和が答え。candies以降の項は漸化式には含めない。

public class TheDiceGame {

	public double expectedThrows(int candies) {
		double[] dp = new double[candies+7];
		double[] ep = new double[candies+7];
		dp[0] = 1;
		for(int i = 0;i < candies;i++){
			for(int j = 1;j <= 6;j++){
				dp[i+j] += dp[i] / 6;
				ep[i+j] += (ep[i]+dp[i])/6;
			}
		}
		double e = 0;
		for(int i = candies;i < candies + 6;i++){
			e += ep[i];
		}
		return e;
	}

}

1000

m(<=50)個の整数(1<=*<=10^9)が与えられる。これらから合計n(m<=n<=50)個、最低1個ずつ数字を抜き取って並べ替えて数字をつくるとき、できる最大の数字を求めよ。

まず1個ずつ選んだあとの残りのn-m個について考えると、これは最大の整数ばかりを選べばよい。
これでn個の整数が出揃ったあとにソートするのだが、これがどうやら、2個の文字列x,yについて(x+y) < (y+x)を順序として降順に並べ替えるだけで良いらしい。だがこれが推移律を満たしていることが証明できない・・

import java.util.Arrays;
import java.util.Comparator;

public class TheNumbersLord {

	public String create(int[] numbers, int n) {
		int m = numbers.length;
		String[] strs = new String[n];
		int max = 0;
		for(int i = 0;i < m;i++){
			strs[i] = Integer.toString(numbers[i]);
			max = Math.max(max, numbers[i]);
		}
		for(int i = m;i < n;i++){
			strs[i] = Integer.toString(max);
		}
		
		Arrays.sort(strs, new Comparator<String>(){
			public int compare(String x, String y)
			{
				return -(x+y).compareTo(y+x);
			}
		});
		StringBuilder sb = new StringBuilder();
		for(String s : strs){
			sb.append(s);
		}
		
		return sb.toString();
	}

}