BottomCoder SRM 385 div2

TopCoder

SRM 385 div2

points result time
250 AC 4m
500 AC 8.7m
1000 AC 15.8m

比較的易し目だった。

250

市街地から、N(<=50)個の標識を順に見ていったときの最終的な制限速度を求めよ。標識には3種類あって、数字だけ書いてあればそれを制限速度とし、defaultと書いてあれば、市街地であれば市街地の制限速度(60), そうでなければ郊外の制限速度(90)にする。cityと書いてあれば、市街地と郊外の境界を指す。そして新しいゾーンのデフォルトの制限速度で上書きする。

境界をこえたときの上書きに注意すればあとは本当にやるだけ。

import java.util.Arrays;

public class RussianSpeedLimits {

	public int getCurrentLimit(String[] signs) {
		boolean city = true;
		int cur = 0;
		for(String s : signs){
			if(s.equals("default")){
				if(city){
					cur = 60;
				}else{
					cur = 90;
				}
			}else if(s.equals("city")){
				city = !city;
				if(city){
					cur = 60;
				}else{
					cur = 90;
				}
			}else{
				cur = Integer.parseInt(s);
			}
		}
		return cur;
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

500

N(2<=N<=10)個の単語からなるフレーズがある。すべての単語境界に"_"を埋めて全体の文字数をwidth(<=200)にする。ただし、各単語境界に埋める"_"の個数は、最大のものと最小のものの差が高々1とする。これらを満たすもののうち、文字列全体で辞書順最小のものを答えよ。

"A"<"Z"<"_"<"a"<"z".
まずwidthをN-1で割ってベースとなる個数を求める。これらを埋めた後、余りを1個ずつうまく割り振れば良い。
前から見ていって、i番目の単語境界について、i+1番目の単語の先頭が小文字だったら"_"を1個増やす。また、埋めるべき"_"の数が残った単語境界の数と等しくなったら有無をいわさず"_"を1個増やす。

import java.util.Arrays;

public class UnderscoreJustification {

	public String justifyLine(String[] words, int width) {
		int n = words.length;
		int gap = width;
		for(int i = 0;i < n;i++)gap -= words[i].length();
		int base = gap / (n - 1);
		int rest = gap % (n - 1);
		
		StringBuilder sb = new StringBuilder(words[0]);
		for(int i = 1;i < n;i++){
			for(int j = 0;j < base;j++)sb.append('_');
			if(rest == n - i || (rest > 0 && words[i].charAt(0) >= '_')){
				sb.append('_');
				rest--;
			}
			sb.append(words[i]);
		}
		return sb.toString();
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

1000

あるx(>0),d(>0),kがあって、等差数列x,x+d,..x+(k-1)dについて、これらの和となりうる数をmagic arithmetic progressionと呼ぶ。k(=2,3,4,5)が与えられたとき、区間[left,right](<=10^9)上のmagic arithmetic progressionの個数を求めよ。(意訳)

まず与えられた等差数列の和は(2x+(k-1)d)*k/2=kx+k(k-1)/2*dとなる。a=k,b=k(k-1)/2として、ax+bdで表される数の個数を答えれば良い。まず、ax+bdはgcd(a,b)の倍数なので、sup以下では[sup/gcd(a,b)]個以下存在する。ここから、ax+bdで表されない数を捨てる。a'=a/gcd(a,b), b'=b/gcd(a,b)として、g(a'x+b'd)とすると、a'x+b'dで表せない最大の数はa'b'なので、a'x+b'd<=a'b'の範囲でx,dを回してチェックする。このa'b'は、問題の制約下では高々6なのでオーダーを気にする必要はない。
こうして#(sup)が求まるので、最後に#(right)-#(left-1)を計算すれば良い。

数学、なのかな？これは

import java.util.Arrays;

public class SummingArithmeticProgressions {

	public int howMany(int left, int right, int k) {
		return count(right, k) - count(left-1, k);
	}
	
	public int count(int sup, int k)
	{
		int cx = k;
		int cd = k*(k-1)/2;
		int g = gcd(cx,cd);
		int o = cx/g * cd/g;
		long ok = 0;
		for(int x = 1;x <= o;x++){
			for(int d = 1;d <= o;d++){
				if(x*cx/g+d*cd/g<=o){
					ok |= 1L<<(x*cx/g+d*cd/g);
				}
			}
		}
		
		int no = Math.min(o, sup/g);
		return sup/g - (no - Long.bitCount(ok&((1L<<(no+1))-1)));
	}
	
	int gcd(int a, int b)
	{
		while(b > 0){
			int c = a; a = b; b = c % b;
		}
		return a;
	}

	void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}