BottomCoder SRM 392 div2

SRM 392 div2

points	result	time
250	AC	3m
500	AC	17.5m
1000	AC	25m

500,1000がひどい問題だった。

250

2007年の各月にキャンディをいくつ食べたか(<=1000)が書いてある。キャンディはいつも月末に食べるとして、キャンディを食べるまでの、年始からの日数の平均を答えよ。(意訳)

やるだけですね。累積の取り方と最後のdoubleを忘れなければおっけー。最大でもintの範囲を全然出ないので、全部intで良い。

import java.util.Arrays;

public class AverageCandyLifetime {
	public double getAverage(int[] eatenCandies) {
		int[] mo = {31,28,31,30,31,30,31,31,30,31,30,31};
		long x = 0;
		int num = 0;
		for(int i = 0;i <= 11;i++){
			if(i > 0)mo[i] += mo[i-1];
			x += mo[i] * eatenCandies[i];
			num += eatenCandies[i];
		}
		return (double)x / num;
	}

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

500

2つの文字列s1,s2(||<=50)が与えられる。各文字列にはそれぞれ1個の'*'が入っていて、これは0文字以上の文字列にマッチする。s1,s2を両方満たす最短の文字列を求めよ。存在しないときは"impossible"を返せ。

うわーめんどくせー問題〜というのが第一印象。
まず自分のやり方。s1,s2の*以前と以後を取り出す。ここから、共通prefixと共通suffixがわかるので、これらが一致しない場合"impossible". そして共通prefix,suffixを除くと、{"*〜〜", "〜〜*"}, {"*", "〜〜*〜〜"}, {"*", "*"}の3パターン(逆もある)あるので、それぞれについて最短文字列を計算する。
最初のパターンでは、*〜〜の〜〜の頭と〜〜*の〜〜のケツが最も一致しているものが最短となるので、それをforでまわして調べる。
2つ目のパターンは、*の両翼をただつなげればよい。3つ目は空文字列。
こうしてできた文字列と共通prefix,suffixをつなげればできあがり。

次にこの問題を3分半で解いたPetrのやり方。*のところに?をi(0からはじめる)文字埋め込む。もう一方の文字列には、s1-s2+i(>=0でなければならない)個埋め込んで、二つの文字列の長さを等しくする。そのあと、結果文字列をstrとすると、先頭から1文字ずつ走査して、s1側が?ならs2側の文字をstrに追加、s2側が?ならs1側の文字をstrに追加、s1側、s2側の文字がどちらも?でなければ、一致していればその文字をstrに追加、そうでなければiをインクリメントしてcontinue、とする。そして、strが完成したらそれが答え。iをでっかいところまでまわしてもできなかったら"impossible"とする。
うおおすげぇと思ったけどこれ3分半じゃ絶対かけねぇ！

import java.util.Arrays;

public class TwoStringMasks {
	public String shortestCommon(String s1, String s2) {
		int i1 = s1.indexOf('*');
		int i2 = s2.indexOf('*');
		String pre1 = s1.substring(0, i1);
		String suf1 = s1.substring(i1+1);
		String pre2 = s2.substring(0, i2);
		String suf2 = s2.substring(i2+1);
		int cp = Math.min(pre1.length(), pre2.length());
		int cs = Math.min(suf1.length(), suf2.length());
		if(pre1.length() < pre2.length()){
			if(!pre2.startsWith(pre1)){
				return "impossible";
			}
		}else{
			if(!pre1.startsWith(pre2)){
				return "impossible";
			}
		}
		if(suf1.length() < suf2.length()){
			if(!suf2.endsWith(suf1)){
				return "impossible";
			}
		}else{
			if(!suf1.endsWith(suf2)){
				return "impossible";
			}
		}
		if(s1.length() == cp + cs + 1){
			return pre2 + suf2;
		}
		if(s2.length() == cp + cs + 1){
			return pre1 + suf1;
		}
		if(i1 > i2){
			String f = s1.substring(cp, i1);
			for(int i = s2.length() - cs;i >= i2 + 1;i--){
				String q = s2.substring(i2 + 1, i);
				if(f.endsWith(q)){
					return pre2 + f + s2.substring(i);
				}
			}
		}else if(i1 < i2){
			String f = s2.substring(cp, i2);
			for(int i = s1.length() - cs;i >= i1 + 1;i--){
				String q = s1.substring(i1 + 1, i);
				if(f.endsWith(q)){
					return pre1 + f + s1.substring(i);
				}
			}
		}else{
			return pre1 + suf1;
		}
		return null;
	}

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

1000

n*n(<=10*10)のマスがある。これに0以上d-1(d<=n)以下の整数を埋めこんで、どの行・列も1回以上0〜d-1が現れて、かつそのようなもののうち1行目から文字列化したときに辞書順で最小のものを求めよ。

サンプルが親切じゃなかったら絶対わからなかった問題。試行して答えを出す系の問題だと思う。

先頭からn-d行とn-d列は一意に決まり、0 0 0 1 2 3 … d-1 という風になる。残ったd行d列に、各行各列、0〜d-1が1回ずつ現れるようにすれば良い。
残った各行はd個の順列で表せる。そしてnextPermutationで回す順に辞書順となっている。nextPermutationで回して、すでに埋まった行と数字がかぶってなければそれを採用。というふうにしてn-d+1行目から埋めていけば良い。

これで正解だったけれど、なぜこれで正解が出るのか謎。少なくともコンテスト中では証明できないよなぁ。

import java.util.Arrays;

public class QuasiLatinSquares {
	public String[] makeSquare(int n, int d) {
		int[][] b = new int[n][n];
		int u = n - d;
		for(int i = 0;i < u;i++){
			for(int j = 0;j < n;j++){
				b[i][j] = b[j][i] = Math.max(0, j - u);
			}
		}
		
		int[] used = new int[d];
		for(int i = u;i < n;i++){
			int[] ord = new int[d];
			for(int j = 0;j < d;j++)ord[j] = j;
			outer:
			do{
				for(int j = 0;j < d;j++){
					if((used[j]&1<<ord[j])!=0){
						continue outer;
					}
				}
				for(int j = 0;j < d;j++){
					used[j]|=1<<ord[j];
					b[i][j+u] = ord[j];
				}
				break;
			}while(nextPermutation(ord));
		}
		
		String[] ret = new String[n];
		for(int i = 0;i < n;i++){
			StringBuilder sb = new StringBuilder();
			for(int j = 0;j < n;j++){
				sb.append(b[i][j]);
				if(j < n - 1)sb.append(" ");
			}
			ret[i] = sb.toString();
		}
		
		return ret;
	}
	
	public static boolean nextPermutation(int[] src)
	{
		int i;
		for(i = src.length - 2;i >= 0 && src[i] > src[i+1];i--);
		if(i == -1)return false;
		int j;
		for(j = i + 1;j < src.length && src[i] < src[j];j++);
		int d = src[i]; src[i] = src[j - 1]; src[j - 1] = d;
		for(int p = i + 1, q = src.length - 1;p < q;p++,q--){
			d = src[p]; src[p] = src[q]; src[q] = d;
		}
		return true;
	}

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