BottomCoder SRM401 div2

SRM 401 div2

point	result	time
250	WA1	数分
500	AC(resubmit)	7m
1000	WA∞	2h

本番でこんなことやったら即死級のひどさだった。

250

与えられた線分(x1,y1)-(x2,y2)(0<=x1,y1,x2,y2<=50, int)の端点以外にある格子点の個数を求めよ。

はじめにみたとき50という制約の低さが目に入って、forでまわせばいいじゃんと思って書いたのが運の尽き、コピペ置換をミスってWAという結果に・・
実際は座標が等しい場合を場合分けした後gcd(x2-x1,y2-y1)-1を計算するだけで良いのでした。各格子点の座標は(x1+(x2-x1)k/gcd, y1+(y2-y1)k/gcd)で表される(k=1,..,gcd-1)。

最適化版

import java.util.Arrays;

public class DreamingAboutCarrots {
	public int carrotsBetweenCarrots(int x1, int y1, int x2, int y2) {
		if(x1 == x2){
			return Math.max(Math.abs(y2 - y1) - 1, 0);
		}else{
			if(y1 == y2){
				return Math.max(Math.abs(x2 - x1) - 1, 0);
			}else{
				return gcd(Math.abs(x2 - x1), Math.abs(y2 - y1)) - 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(o.length > 1 || o[0].getClass().isArray() ? Arrays.deepToString(o) : o[0]); }
}

誰得

import java.util.Arrays;

public class CopyOfDreamingAboutCarrots {
	public int carrotsBetweenCarrots(int x1, int y1, int x2, int y2) {
		int ct = 0;
		if(x1 < x2){
			for(int i = x1 + 1;i <= x2 - 1;i++){
				double t = (double)(i - x1) / (x2 - x1);
				int j = (int)Math.round(t * (y2 - y1) + y1);
				if((i - x1) * (y2 - y1) == (j - y1) * (x2 - x1)){
					ct++;
				}
			}
		}else if(x1 > x2){
			for(int i = x2 + 1;i <= x1 - 1;i++){
				double t = (double)(i - x1) / (x2 - x1);
				int j = (int)Math.round(t * (y2 - y1) + y1);
				if((i - x1) * (y2 - y1) == (j - y1) * (x2 - x1)){
					ct++;
				}
			}
		}else if(y1 < y2){
			for(int i = y1 + 1;i <= y2 - 1;i++){
				double t = (double)(i - y1) / (y2 - y1);
				int j = (int)Math.round(t * (x2 - x1) + x1);
				if((i - y1) * (x2 - x1) == (j - x1) * (y2 - y1)){
					ct++;
				}
			}
		}else if(y2 < y1){
			for(int i = y2 + 1;i <= y1 - 1;i++){
				double t = (double)(i - y1) / (y2 - y1);
				int j = (int)Math.round(t * (x2 - x1) + x1);
				if((i - y1) * (x2 - x1) == (j - x1) * (y2 - y1)){
					ct++;
				}
			}
		}
		return ct;
	}

	void tr(Object... o) { System.out.println(o.length > 1 || o[0].getClass().isArray() ? Arrays.deepToString(o) : o[0]); }
}

500

n=fieldOrder(<=30)が与えられる。広義単調減少非負数列a_0,a_1,..,a_{n-1}で、任意のiに対しa_i<=n-iを満たすようなものは何通りあるか。

DP. dp[i][j]=(i番目の数列の値がjである組み合わせ)として、
dp[i][j]=Σ_{k=j〜n-(i-1)} dp[i-1][j]
として計算していけば良い。

最初longの罠に気づかず慌ててresubmit. 入力が単純なときは最大ケースをテストしましょう。

import java.util.Arrays;

public class FIELDDiagrams {
	public long countDiagrams(int fieldOrder) {
		int n = fieldOrder;
		long[] dp = new long[n+1];
		for(int i = 1;i <= n;i++){
			dp[i] = 1;
		}
		for(int i = 1;i <= n;i++){
			long[] ndp = new long[n+1-i];
			for(int j = 0;j < n+1-i;j++){
				long sum = 0;
				for(int k = j;k < n+2-i;k++){
					sum += dp[k];
				}
				ndp[j] = sum;
			}
			dp = ndp;
		}
		return dp[0];
	}

	void tr(Object... o) { System.out.println(o.length > 1 || o[0].getClass().isArray() ? Arrays.deepToString(o) : o[0]); }
}

1000

長さN(<=1000000)の文字列が与えられる。この文字列が文字列Aの繰り返しの一部であるとき、Aの最小の長さを求めよ。

これは知らなかったのでわからなかった。こういう最小周期を求めるものは、KMP検索で使うテーブルをつくって、N-kmptable[N]を求めれば良い。kmptable[N]の値は、文字列のk文字のprefix=k文字のsuffix, k

import java.util.Arrays;

public class RunningLetters {
	public int newsLength(String[] running) {
		StringBuilder sb = new StringBuilder();
		for(String s : running){
			sb.append(s);
		}
		StringBuilder sbs = new StringBuilder();
		String[] sp = sb.toString().split(" ");
		for(int i = 0;i < sp.length;i+=2){
			int count = Integer.parseInt(sp[i]);
			for(int j = 0;j < count;j++){
				sbs.append(sp[i+1]);
			}
		}
		
		char[] q = sbs.toString().toCharArray();
		int n = q.length;
		
		int[] kmp = new int[n+1];
		kmp[0] = -1; kmp[1] = 0;
		for(int i = 2, j = 0;i <= n;i++){
			while(j > 0 && q[i-1] != q[j])j = kmp[j];
			kmp[i] = q[i-1] == q[j] ? ++j : 0;
		}
		return n - kmp[n];
	}
	
	void tr(Object... o) { System.out.println(o.length > 1 || o[0].getClass().isArray() ? Arrays.deepToString(o) : o[0]); }
}