BottomCoder SRM 403 div2

TopCoder

SRM403 div2

point result time
250 AC ?
500 AC ?
1000 WA∞,TLE∞,MLE 2h30m

1000は爆死した。典型的な問題っぽいので解き方はおぼえておきたい。

Vasyl回。timeはログが流れて消えてしまったけど250,500は10,20分以内だったとおもう。

250

n(4<=n<=1000000)以下の最大のlucky numberを求めよ。lucky numberとは4または7だけで構成される数のことである。

全走査でも間に合いそうなので全走査。n=1のとき-4とか出すのかなとか思ったらそんなことはなかった。

public class TheLargestLuckyNumber {

	public int find(int n) {
		outer:
		for(int i = n;i >= 4;i--){
			for(int j = i;j > 0;j /= 10){
				if(!(j % 10 == 4 || j % 10 == 7)){
					continue outer;
				}
			}
			return i;
		}
		return 4;
	}

}

500

区間[a,b](a<=b<=10^9)にあるlucky numberの総数を求めよ。lucky numberとは(ry

桁数ごとにわけてから再帰。実はn桁のlucky numberの総数は2^nしかないので、適当に全列挙したあと全走査で求めてもいいかもしれない。

public class TheLuckyNumbers {

	public int count(int a, int b) {
		int inf = a;
		int sup = b;
		int sum = 0;
		for(int i = 10;i <= 1000000000;i *= 10){
			if(inf < i){
				if(sup <= i){
					sum += rec(inf, sup, i/10);
					break;
				}else{
					sum += rec(inf, i, i/10);
				}
				inf = i;
			}
		}
		return sum;
	}
	
	int rec(int a, int b, int d)
	{
		if(d == 1){
			int ct = 0;
			if(a <= 4 && b >= 4)ct++;
			if(a <= 7 && b >= 7)ct++;
			return ct;
		}
		
		int ret = 0;
		if(a / d <= 4 && b / d >= 4){
			ret += rec(Math.max(a - 4 * d, 0), Math.min(b - 4 * d, d), d/10);
		}
		if(a / d <= 7 && b / d >= 7){
			ret += rec(Math.max(a - 7*d, 0), Math.min(b - 7*d, d), d/10);
		}
		return ret;
	}
}

1000

合計してちょうどn(<=1000000)になるようなlucky numberの和を表す昇順の配列(重複を許す)のうち、長さ最小で、その中で配列を前から比べたときに最小になるものを答えよ。lucky numberとは(ry

爆死した問題。lucky numberの総数はたかだか126個なので単なる履歴付きchange-making(和に関するDP)かと思いきや、ある和になる最適な配列をすべてとっておくとMLEになる。(@matsu4512のはなぜかOKだったらしいけど)
というわけで最新のものだけを持たせておいて履歴をたどらせる形になるが、それでも最大ケースでTLEしてしまう。もしくはWA.
わけがわからなかったので、@ogiekako氏のコードをみながら考えた。

まず長さでDPする。[x] = (xを和とする最適な配列の最小の長さ)
このあと、nから、ln=lucky numberを小さい順にみていって、[n]-[n-ln]=1となるものがあれば、そのlnを出力配列に加える。そして、次はn-lnに対して同様の走査を行う。

分かった途端驚嘆した・・最適な配列があるならば、最小のlucky numberを抜いたものもまた最適のはず、という考え方か。最小のものから抜いていくのでもちろん問題の条件は満たされる。
多分ここまでわからないとJavaでは解けないのだろう。ひらめきではなくテクニックっぽいものだと思ったのでおぼえておきたい。

import java.util.Arrays;

public class TheSumOfLuckyNumbers {

	public int[] sum(int n) {
		int[] ln = new int[200];
		int p = 0;
		for(int i = 1;i <= n;i++){
			if(islucky(i)){
				ln[p++] = i;
			}
		}
		
		int[] dlen = new int[n+1];
		Arrays.fill(dlen, -1);
		dlen[0] = 0;
		for(int i = 1;i <= n;i++){
			int min = 99999999;
			for(int j = 0;j < p && ln[j] <= i;j++){
				min = Math.min(min, dlen[i-ln[j]]);
			}
			dlen[i] = min+1;
		}
		
		if(dlen[n] >= 99999999)return new int[0];
		int[] ret = new int[dlen[n]];
		int pp = 0;
		for(int u = n;u != 0;){
			for(int j = 0;j < p && ln[j] <= u;j++){
				if(dlen[u] == dlen[u-ln[j]] + 1){
					ret[pp++] = ln[j];
					u -= ln[j];
					break;
				}
			}
		}
		return ret;
	}
	
	public boolean islucky(int n)
	{
		for(int i = n;i > 0;i/=10){
			if(!(i % 10 == 4 || i % 10 == 7)){
				return false;
			}
		}
		return true;
	}

}