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になると思ってるんじゃないよ(憤怒)