よくわからないけど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って解けるんですか 数学できないと出来ないんですか?)