SRM605
easy: てきとうなぎにgreedyするだけ。
#include<stdio.h> #include<vector> #include<algorithm> #include<map> using namespace std; int maxi[100]; int ps[100]; class AlienAndHamburgers { public: int getNumber(vector<int>typ,vector<int>vec) { fill(maxi,maxi+100,-200000); for(int i=0;i<typ.size();i++) { maxi[typ[i]-1]=max(maxi[typ[i]-1],vec[i]); if(vec[i]>0) { ps[typ[i]-1]+=vec[i]; } } vector<int>ret; for(int i=0;i<100;i++) { if(maxi[i]!=-200000) { if(ps[i]!=0) { ret.push_back(ps[i]); } else { ret.push_back(maxi[i]); } } } sort(ret.begin(),ret.end()); reverse(ret.begin(),ret.end()); int ans=0; for(int i=0;i<=ret.size();i++) { int sum=0; for(int j=0;j<i;j++) { sum+=ret[j]; } ans=max(ans,sum*i); } return ans; } };
med: てきとうなぎにbitDPするだけ。特に難しいところはないのにだらだら実装して時間がかかったのは最近数学しかしてないからに違いない(全盛期なら20分あれば実装できそう)
K<=10みたいな重要なことはもっと強調するべきだと思う。
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll dp[101][201][1024]; ll mod=1000000007; class AlienAndSetDiv1 { public: int cntz(int a,int n) { int ret=n; for(int i=0;i<n;i++) { ret-=a%2; a/=2; } return ret; } int getNumber(int num,int gen) { dp[0][100][0]=1; for(int i=0;i<num*2;i++) { for(int j=-i;j<=i;j++) { for(int k=0;k<(1<<gen);k++) { //printf("%d %d %d %lld %d %d %d %d\n",i,j,k,dp[i][j+100][k],j-1,(k<<1)%(1<<gen)+1,j+1,(k<<1)%(1<<gen)); if(j<(-gen)) { dp[i+1][j+100+1][(k<<1)%(1<<gen)]+=dp[i][j+100][k]; } if(j>gen) { dp[i+1][j+100-1][(k<<1)%(1<<gen)+1]+=dp[i][j+100][k]; } if(j<0) { dp[i+1][j+100-1][(k<<1)%(1<<gen)+1]+=dp[i][j+100][k]; } if(j>0) { dp[i+1][j+100+1][(k<<1)%(1<<gen)]+=dp[i][j+100][k]; } if(j==0) { dp[i+1][j+100+1][(k<<1)%(1<<gen)]+=dp[i][j+100][k]; dp[i+1][j+100-1][(k<<1)%(1<<gen)+1]+=dp[i][j+100][k]; } if(j<0&&j>=(-gen)) { if(gen-1-cntz(k%(1<<(gen-1)),gen-1)<(-j)) { dp[i+1][j+100+1][(k<<1)%(1<<gen)]+=dp[i][j+100][k]; } } if(j>0&&j<=gen) { if(cntz(k%(1<<(gen-1)),gen-1)<j) { dp[i+1][j+100-1][(k<<1)%(1<<gen)+1]+=dp[i][j+100][k]; } } dp[i+1][j+100+1][(k<<1)%(1<<gen)]%=mod; dp[i+1][j+100-1][(k<<1)%(1<<gen)+1]%=mod; } } } ll ans=0; for(int i=0;i<(1<<gen);i++) { ans+=dp[num*2][100][i]; } ans%=mod; return ans; } };
hard: しらん
1899->1984(+85) まともな(人間として恥ずかしくない)レートに近づいてきた(まだ足りない)
なぜか部屋1位。まあ青14人だししょうがないね。
人間に解ける問題は見た瞬間解法が分かる問題だったのでただの実装コンテストだった。準急さんプロ。