読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

SRM454 DIV2

眠気に襲われながらも参加。
250pt submit
500pt submit
1000pt closed
Challenges なし

250pt

201.46 / 250 pt
与えられたCの桁和とAからBの範囲の値で桁和の差が最小になるような値を求める。
つまらないミスで時間ロスした。これは240pt取ってないとだめだorz

500pt

150 / 500 pt
指定された文字列がgridの行or列を入れ替えて、縦(左から右)か横方向(上から下)に
生成出来るときは入れ替えの最小回数、生成出来ないときは-1
実装問題。
素直に実装したは良いが、終了間際になって同じ文字が複数出現した文字列の場合に
対応してないことに気付き、急いで修正再提出。ポイントは最低の150になったが、SystemPassして良かった。


計 351.46pt
rate 896→983(+87

んー、やはり問題文を理解出来るかどうかによるレートの上下はなんとかしたいw

// 250pt
class MinimalDifference{
public:
	int sumd(int x)
	{
		int d=0;
		for(;x;x/=10)d+=x%10;
		return d;
	}
	int findNumber(int A, int B, int C)
	{
		int c=sumd(C);
		int ans=0;;
		int m=1000000001;
		for(int a=A;a<=B;a++){
			if(m>abs(c-sumd(a))){
				m=abs(c-sumd(a));
				ans=a;
			}
		}
		return ans;
	}
};


// 500pt
class WordsGame
{
public:
	int minimumSwaps(vector <string> grid, string word)
	{
		unsigned char C[256];
		int ans1,ans2,flag1,flag2;
		flag1=flag2=0;
		ans1=ans2=10000;
		memset(C,0,sizeof(C));
		for(int i=0;i<word.size();i++)C[word[i]]++;
		
		for(int i=0;i<grid.size();i++){
			int cnt1,cnt2;
			cnt1=cnt2=0;
			unsigned char CC1[256],CC2[256];
			memset(CC1,0,sizeof(CC1));
			memset(CC2,0,sizeof(CC2));
			for(int j=0;j<grid[i].size();j++){
				if(C[grid[i][j]])CC1[grid[i][j]]++;
				if(C[grid[j][i]])CC2[grid[j][i]]++;
			}
			int j;
			for(j=0;j<256 && C[j]==CC1[j];j++);
			if(j==256)cnt1=1;
			for(j=0;j<256 && C[j]==CC2[j];j++);
			if(j==256)cnt2=1;
			
			if(cnt1){
				flag1=1;
				int tmp=0;
				vector<string> gg=grid;
				for(int k=0;k<word.size()-1;k++){
					if(word[k]==gg[i][k])continue;
					int p;
					for(p=k+1;p<word.size()&&word[k]!=gg[i][p];p++);
					swap(gg[i][k],gg[i][p]);
					tmp++;
				}
				ans1=min(ans1,tmp);
			}
			if(cnt2){
				flag2=1;
				int tmp=0;
				vector<string> gg2=grid;
				for(int k=0;k<word.size()-1;k++){
					if(word[k]==gg2[k][i])continue;
					int p;
					for(p=k+1;p<word.size()&&word[k]!=gg2[p][i];p++);
					swap(gg2[k][i],gg2[p][i]);
					tmp++;
				}
				ans2=min(ans2,tmp);
			}
		}
		if(flag1&&flag2)return min(ans1,ans2);
		else if(flag1) return ans1;
		else if(flag2) return ans2;
		else return -1;
	}
};