BottomCoder SRM 375 div2

TopCoder

SRM 375 div2

points result time
250 AC 5m
500 AC 12m
1000 AC 9.5m

やさしめでした。

250

原料(||<=50)の容積(ml)と質量(g)が文章で与えられる。すべての原料を混ぜ合わせたときの密度(g/ml)を答えよ。

制約がやたら多い割にはやることは簡単。決まったフォーマットの文章から数字を取り出して和を求めて割れば良い。
文章の中間はいろんな形態がとれるので、ぱぱっと正規表現を使いました。

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class MixtureDensity {

	public double getDensity(String[] ingredients) {
		Pattern p = Pattern.compile("^([0-9]+) .* ([0-9]+) g$");
		int num = 0;
		int den = 0;
		for(String s : ingredients){
			Matcher m = p.matcher(s);
			if(m.find()){
				num += Integer.parseInt(m.group(2));
				den += Integer.parseInt(m.group(1));
			}
		}
		return (double)num / (double)den;
	}

}

500

n*n(<=8*8)の盤のinitPositionの位置にDukeの駒が置かれている。この駒は上下左右に1マスずつ動ける。このDukeが同じマスを通らないように動きまわる時(全てのマスを通るとかいう必要はない)、通ったパスを表す文字列のうちの辞書順最大のものを答えよ。

答えるべきパスは「(列)(行)-(列)(行)-...」といった感じ。これを最大化するときは、列を+1するほうに動かすのを優先すれば良い。同様に考えて、右上下左の優先順位でDukeを動かす。
あとは再帰で最大のパスを探索する。優先順位は枝刈りに使う。すでに最大のパスがあったとき、現在の動きからどうやっても最大に成り得ない場合ぶったぎる。

public class DukeOnChessBoard {
	boolean[][] visited;
	int n;

	public String dukePath(int n, String initPosition) {
		visited = new boolean[n][n];
		this.n = n;
		visited[initPosition.charAt(0)-'a'][initPosition.charAt(1)-'1'] = true;
		String ret = initPosition + rec(initPosition.charAt(0)-'a', initPosition.charAt(1)-'1');
		if(ret.length() > 40){
			ret = ret.substring(0, 20) + "..." + ret.substring(ret.length() - 20);
		}
		
		return ret;
	}
	
	int[] dc = {1, 0, 0, -1};
	int[] dr = {0, 1, -1, 0};

	public String rec(int c, int r)
	{
		String ret = "";
		for(int i = 0;i < 4;i++){
			int nc = c + dc[i];
			int nr = r + dr[i];
			String m = "-" + (char)(nc+'a') + (char)(nr+'1');
			if(nc >= 0 && nc < n && nr >= 0 && nr < n && !visited[nc][nr] && ret.compareTo(m + "~") < 0){
				visited[nc][nr] = true;
				String v = m + rec(nc, nr);
				if(ret.compareTo(v) < 0){
					ret = v;
				}
				visited[nc][nr] = false;
			}
		}
		return ret;
	}
	
}

1000

n(1<=n<=10^9)が与えられる。nではじまる数で、nの0以外のどの桁の数字でも割り切れる最小の数を求めよ。

まずnの桁を列挙してlcmを計算する。これは高々lcm(2〜9)=2520. そしてnのあとに続く桁数の小さい方から、lcmで割り切れる数が[n*i,n*i+i-1]の範囲にあるかどうかチェックする。(i=1,10,100,..)

別にlcmを求めなくてもよかったりする。いろんな解法があるね。

public class DivisibleByDigits {

	public long getContinuation(int n) {
		int lcm = 1;
		for(int i = n;i > 0;i /= 10){
			int d = i % 10;
			if(d > 0){
				lcm = lcm * d / gcd(lcm, d);
			}
		}
		
		for(long i = 1;;i *= 10){
			long inf = ((long)n*i) % lcm;
			System.out.println(i + " " + inf);
			if(inf == 0){
				return (long)n*i;
			}else{
				long il = ((long)n*i) - inf + lcm;
				if(il <= (long)n*i+i-1)return il;
			}
		}
		
//		return 0;
	}
	
	public int gcd(int a, int b)
	{
		while(b > 0){
			int c = a; a = b; b = c % b;
		}
		return a;
	}

}