Member SRM 501

よくわからないけどwrongさんがwriter。なんで京都から出来るんだろう…

250:FoxFailedSystemTestDivOne
Cielが何かをしています。わかりません。

普通にDP書くけどよく分からないし適当にサンプルとおったから送りつけてみる。
ChallengeでGreedyしてる人がいる。なんだGreedyか。じゃあ落ちるな→落ちる

ここ最近EasyのGreedyが多すぎませんか? Greedyが決まって出来ない人のことを考えてないと思います。

500:FoxMakeDynamicProgramming
CielがDPでソースコードを書いて送ったら通りました。

public class FoxAverageSequence{
	public int theCount(int[]a){
		int dp0[][][]=new int[a.length][41][1601];
		int dp1[][][]=new int[a.length][41][1601];
		int MOD=1000000007;
		if(a[0]!=-1){
			dp0[0][a[0]][a[0]]=1;
		}else{
			for(int i=0;i<=40;i++)dp0[0][i][i]=1;
		}
		for(int i=1;i<a.length;i++){
			if(a[i]!=-1){
				for(int j=0;j<=40;j++){
					for(int k=a[i]*i+a[i];k<=1600;k++){
						if(a[i]>=j){
							dp0[i][a[i]][k]=(dp0[i][a[i]][k]+dp0[i-1][j][k-a[i]])%MOD;
							dp0[i][a[i]][k]=(dp0[i][a[i]][k]+dp1[i-1][j][k-a[i]])%MOD;
						}else{
							dp1[i][a[i]][k]=(dp1[i][a[i]][k]+dp0[i-1][j][k-a[i]])%MOD;
						}
					}
				}
			}else{
				for(int j=0;j<=40;j++){
					for(int k=0;k<=40;k++){
						for(int l=j*i+j;l<=1600;l++){
							if(j>=k){
								dp0[i][j][l]=(dp0[i][j][l]+dp0[i-1][k][l-j])%MOD;
								dp0[i][j][l]=(dp0[i][j][l]+dp1[i-1][k][l-j])%MOD;
							}else{
								dp1[i][j][l]=(dp1[i][j][l]+dp0[i-1][k][l-j])%MOD;
							}
						}
					}
				}
			}
		}
		int ret=0;
		for(int i=0;i<=40;i++)
			for(int j=0;j<=1600;j++){
				ret=(ret+dp0[a.length-1][i][j])%MOD;
				ret=(ret+dp1[a.length-1][i][j])%MOD;
			//	if(j<10)System.out.println(i+" "+j+" "+dp0[a.length-1][i][j]+" "+dp1[a.length-1][i][j]);
			}
		return ret;
	}
}

1000:FoxCannotReadProblem

きつねには問題文がよめませんでした。おわり。

ChallengePhase

ちょっと僕には難しいです

SystemTest

Easyを落とすというのはいつものことです。
あとMediumとおりました。

Result

0 + 271.05 + 0 + 0 = 271.05 (267th)
Rating: 1353 -> 1431 (-INF)

徐々に色つきコーダーが近づいてきました。
いい加減Greedy出すのやめてくださいorz 全体的には良問なのですが……
(どうやったらGreedyって解けるんですか 数学できないと出来ないんですか?)