BottomCoder SRM 398 div2

SRM 398 div2

point	result	time
250	AC	2m
500	AC	7m
900	AC	9.5m

@chokudai氏がきていて無駄に緊張した。

250

整数A,X,Y,M(1<=*<=10000),n(2<=*<=10000)が与えられ、数列Aが
A[0] = A0
A[i] = (A[i - 1] * X + Y) MOD M, for 0 < i < n
で定義される。Aの任意の2項の差の絶対値の最小値を求めよ。

数列をつくってからソートして、そのうちの隣接する2項の差の絶対値をとっていって最小値を出力すればよい。MOD前の()でもintの範囲をこえないのですべてintでOK.

import java.util.Arrays;

public class MinDifference {

	public int closestElements(int A0, int X, int Y, int M, int n) {
		int[] a = new int[n];
		a[0] = A0;
		for(int i = 1;i < n;i++){
			a[i] = (a[i-1] * X + Y) % M;
		}
		Arrays.sort(a);
		
		int min = 9999999;
		for(int i = 0;i < n - 1;i++){
			min = Math.min(min, a[i+1] - a[i]);
		}
		return min;
	}

}

500

2つの数x,y(||<=100, x!=y)を2回ずつ使い、各数字の間にそれぞれ+-*のどれかを置いて数式をつくる。できあがった数式のうち、前から計算(演算子の優先順位は無視)してval(||<=10^8)と等しくなるような数式の個数はいくつか。

数字の置き方は6通り、演算子の置き方は3^3通りなので全探索でOK.さらに、6,3,3,3通りは独立なので、4重forでいける。演算を1個の関数にまとめておけば楽に書けるかな？

public class CountExpressions {

	public int calcExpressions(int x, int y, int val) {
		int ct = 0;
		for(int i = 0;i < 16;i++){
			if(Integer.bitCount(i) == 2){
				int[] v = new int[4];
				for(int j = 0;j < 4;j++){
					v[j] = (i>>j)%2 == 0 ? x : y;
				}
				long ret = v[0];
				for(int a = 0;a < 3;a++){
					long ret2 = cal(a, ret, v[1]);
					
					for(int b = 0;b < 3;b++){
						long ret3 = cal(b, ret2, v[2]);
						for(int c = 0;c < 3;c++){
							long ret4 = cal(c, ret3, v[3]);
							if(ret4 == val){
								ct++;
							}
						}
					}
				}
			}
		}
		return ct;
	}
	
	long cal(int k, long a, long b)
	{
		if(k == 0){
			return a + b;
		}else if(k == 1){
			return a - b;
		}else if(k == 2){
			return a * b;
		}
		return 0;
	}

}

900

文字列配列matchWords(||<=50, 文字列の長さ<=50)と、この要素数と長さが等しい文字列matchStringが与えられる。文字列配列をこの順に並べていくつかの文字列を右にずらして、どこかの位置に、縦にmatchStringができあがるようにしたい。ずらす文字数の合計の最小値を求めよ。出来上がらない場合は-1を返せ。

サンプルをみると題意が一発でわかる問題。
各文字列matchWords[i]でmatchString[i]と一致する文字の出現位置を列挙しておく。出現しない場合は-1を返す。
列挙したあと、matchStringがそろうindexは高々50-1なので、そろうindexについて走査。各matchWordsについてindex以下の最大の出現位置を求めて、最小ずらし数を計算。これを合計したものを最小化すればよい。オーダーは、列挙したものがソートされているのでO(N^2 log N)でいける。
Arrays.binarySearchのインデックス指定版を最初使っていたのだが、これがJDK1.5にはなかったようで焦った。配列全体版はある。

そろうindexは多分一致する文字の出現位置のどれかになると思うけど、今回は関係なかった。

import java.util.Arrays;

public class MatchString {

	public int placeWords(String matchString, String[] matchWords) {
		int n = matchWords.length;
		int[][] mind = new int[n][];
		int[] p = new int[n];
		for(int i = 0;i < n;i++){
			int[] mr = new int[50];
			for(int j = 0;j < matchWords[i].length();j++){
				if(matchWords[i].charAt(j) == matchString.charAt(i)){
					mr[p[i]++] = j;
				}
			}
			if(p[i] == 0){
				return -1;
			}
			mind[i] = new int[p[i]];
			for(int j = 0;j < p[i];j++){
				mind[i][j] = mr[j];
			}
		}
		
		int min = 99999999;
		outer:
		for(int i = 0;i < 101;i++){
			int s = 0;
			for(int j = 0;j < n;j++){
				int ind = Arrays.binarySearch(mind[j], i);
				if(ind < 0){
					ind = -ind - 2;
					if(ind < 0)continue outer;
					s += i - mind[j][ind];
				}
			}
			min = Math.min(min, s);
		}
		if(min == 99999999)return -1;
		return min;
	}

}