SRM551
easy:やるだけ
#include<stdio.h> #include "stdafx.h" #include<vector> #include<iostream> #include<algorithm> #include<string> using namespace std; int main() { string str; cin>>str; int hai[26]; fill(hai,hai+26,0); for(int i=0;i<str.size();i++) { hai[str[i]-'A']++; } int num=0; for(int i=0;i<26;i++) { if(hai[i]) { num++; } } int ret; if(num==1) { ret=1; } if(num==2) { ret=2; } if(num>=3) { ret=0; } printf("%d\n",ret); }
medium:全文字に対して貪欲につなげて最小値をとる。
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; int main() { string str; int num; cin>>str; scanf("%d",&num); int maxi=0; for(int i=0;i<str.size();i++) { vector<int>vec; int flag=1; for(int j=i-1;j>=0;j--) { if(str[i]==str[j]) { vec.push_back(i-j-flag); flag++; } } flag=1; for(int j=i+1;j<str.size();j++) { if(str[i]==str[j]) { vec.push_back(j-i-flag); flag++; } } sort(vec.begin(),vec.end()); int ans=0; int sum=0; for(int j=0;j<vec.size();j++) { if(sum<=num) { ans++; } sum+=vec[j]; } if(sum<=num) { ans++; } maxi=max(maxi,ans); } printf("%d\n",maxi); }
hard:数学ゲーに見える。でも実はDPするだけ。
#include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; typedef long long ll; ll mod=1000000007; ll dp[51][51][51][3][3]; int main() { string str; cin>>str; int numa=0,numb=0,numc=0; for(int i=0;i<str.size();i++) { if(str[i]=='A') { numa++; } if(str[i]=='B') { numb++; } if(str[i]=='C') { numc++; } } for(int i=0;i<51;i++) { for(int j=0;j<51;j++) { for(int k=0;k<51;k++) { for(int l=0;l<3;l++) { for(int m=0;m<3;m++) { dp[i][j][k][l][m]=0; } } } } } dp[1][0][0][0][0]=1; dp[0][1][0][1][1]=1; dp[0][0][1][2][2]=1; for(int i=0;i<=numa;i++) { for(int j=0;j<=numb;j++) { for(int k=0;k<=numc;k++) { if(i+j+k<=1) { continue; } for(int m=0;m<3;m++) { if(i!=0) { dp[i][j][k][0][m]=dp[i-1][j][k][1][m]+dp[i-1][j][k][2][m]; } if(j!=0) { dp[i][j][k][1][m]=dp[i][j-1][k][0][m]+dp[i][j-1][k][2][m]; } if(k!=0) { dp[i][j][k][2][m]=dp[i][j][k-1][0][m]+dp[i][j][k-1][1][m]; } dp[i][j][k][0][m]%=mod; dp[i][j][k][1][m]%=mod; dp[i][j][k][2][m]%=mod; } } } } ll ret=dp[numa][numb][numc][0][1]+dp[numa][numb][numc][0][2]+dp[numa][numb][numc][1][0]+dp[numa][numb][numc][1][2]+dp[numa][numb][numc][2][0]+dp[numa][numb][numc][2][1]; ret%=mod; printf("%d\n",int(ret)); }
例によって手元のコードを張っているのでちょっと違うのは勘弁。
challenge:見るからにやばいeasyを1つおとす。やばさが自分の発想の域を超えていてchallenge1ミスしてしまった。どうやったらあんなコードになるのか
結果:全部通って4位。
実はD2hard通したのはじめてだったり。
rate:1098->1331(+233)
D2有終の美を飾ったことにしたい(意訳:もうDiv2には落ちたくない)
なんでもDPだせばD2hardになると思ってるんじゃないよ(憤怒)