Codeforces Round #131 (Div. 2)

久々にCFに出てみました。

A.
全探索。
余計なことを考えずに、a,bが0から1000までの場合をすべて確かめる。

int main(){
	int n,m,ans=0;
	cin>>n>>m;
	for(int i = 0; i <= 1000; i++){
		for(int j = 0; j <= 1000; j++){
			if(i*i+j==n&&i+j*j==m)ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

B.
ベタベタ書きました。

0がない場合 -> -1
和を3で割った余りが1の場合 -> 余りが1のやつを1つ消す。出来なければ、余りが2のやつを2つ消す。どちらも、小さい順に見ていく
和を3で割った余りが2の場合 -> 上と同じような感じ
3で割り切れる場合 -> そのまま

その後、0以外何も残らなかったら0を1つだけ出力して、それ以外の場合は数字が大きい方から出力する。

int d[10];

int main(){
	int n;
	cin>>n;
	for(int i = 0; i < n; i++){
		int a;
		cin>>a;
		d[a]++;
	}
	int sum=0;
	if(!d[0]){
		cout<<-1<<endl;
		return 0;
	}
	for(int i = 0; i < 10; i++){
		sum += d[i]*i;
	}
	if(sum%3==1){
		if(d[1])d[1]--;
		else if(d[4])d[4]--;
		else if(d[7])d[7]--;
		else if(d[2]+d[5]+d[8]<2){
			cout<<0<<endl;
			return 0;
		}else {
			int t=2;
			while(t){
				if(d[2])d[2]--;
				else if(d[5])d[5]--;
				else if(d[8])d[8]--;
				t--;
			}
		}
	}
	if(sum%3==2){
		if(d[2])d[2]--;
		else if(d[5])d[5]--;
		else if(d[8])d[8]--;
		else if(d[1]+d[4]+d[7]<2){
			cout<<0<<endl;
			return 0;
		}else {
			int t=2;
			while(t){
				if(d[1])d[1]--;
				else if(d[4])d[4]--;
				else if(d[7])d[7]--;
				t--;
			}
		}
	}
	sum = 0;
	for(int i = 0; i < 10; i++){
		sum += d[i]*i;
	}
	for(int i = 9; i >= 0; i--){
		for(int j = 0; j < d[i]; j++){
			if(i!=0||sum)cout<<i;
			else{
				cout<<0;
				break;
			}
		}
	}
	
	cout<<endl;
	return 0;
}

C.
D.
E.
hackしてたら時間が足りなくて解けなかった。
CとEは解けるかもしれない問題だったから、解いたほうが良かったかもしれない。

C.(追記)
読解が難しそうで、配点が大きいから難しいと思い込んでいましたが、解いてみたら簡単でした。2000点だったので、かなりもったいない。仕方がないことですが。

コンピュータは3つしかないから、最初どれにするかは全て試す。
その後、1→2→3→1の順で移動して、更新できなくなるまで更新する。
一番良い解を出力する。

int c[200],n;
vector<int> d[200];
bool used[200];

int solve(int t){
	memset(used,0,sizeof(used));
	int uc=0,ans=0;
	while(uc<n){
		bool udf=true;
		while(udf){
			udf=false;
			for(int i = 0; i < n; i++){
				if(c[i]==t){
					bool flag=!used[i];
					for(int j = 0; j < d[i].size(); j++){
						if(!used[d[i][j]]){
							flag=false;
							break;
						}
					}
					if(flag){
						used[i]=true;
						udf=true;
						ans++;
						uc++;
					}
				}
			}
		}
		t=t%3+1;
		ans++;
	}
	return ans-1;
}

int main(){
	int ans=1<<10;
	cin>>n;
	for(int i = 0; i < n; i++)cin>>c[i];
	for(int i = 0; i < n; i++){
		int k;
		cin>>k;
		for(int j = 0; j < k; j++){
			int a;
			cin>>a;
			d[i].push_back(a-1);
		}
	}
	for(int i = 1; i <= 3; i++)ans=min(ans,solve(i));
	cout<<ans<<endl;
	return 0;
}

E.(追記)
DPです。
4次元配列を3次元配列にする発想が無くて解けませんでしたが、実装は難しくありませんでした。

2人とも(0,0)からスタートすると考えて、2人とも同時に動かしていく。歩く距離は2人とも常に同じなので、配列の次元を1次元下げられる。
DP[1人目のx座標][1人目のy座標][2人目のx座標]:=(0,0)からその2点まで移動したときの得点の最大値
とすると、2人目のy座標が分かる。
2人目のx座標は常に1人目のx座標以下になるようにして(しなくても大丈夫かもしれない)、同じ点に行くときだけ2回分数えないようにすれば解ける。

int g[300][300],dp[300][300][300],dx[]={1,0},dy[]={0,1};
const int INF = 1<<28;

int main(){
	int n;
	cin>>n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin>>g[i][j];
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				dp[i][j][k]=-INF;
			}
		}
	}
	
	dp[0][0][0]=g[0][0];
	for(int i = 0; i < 2*n-2; i++){
		for(int j = max(0,i-n+1); j <= min(i,n-1); j++){
			for(int k = max(0,i-n+1); k <= j; k++){
				for(int l = 0; l < 4; l++){
					int x1=j+dx[l/2],y1=i-j+dy[l/2],x2=k+dx[l%2],y2=i-k+dy[l%2];
					if(x1<n&&y1<n&&x2<n&&y2<n){
						if(x1==x2){
							dp[x1][y1][x2]=max(dp[x1][y1][x2],dp[j][i-j][k]+g[x1][y1]);
						}else {
							dp[x1][y1][x2]=max(dp[x1][y1][x2],dp[j][i-j][k]+g[x1][y1]+g[x2][y2]);
						}
					}
				}
			}
		}
	}
	cout<<dp[n-1][n-1][n-1]<<endl;
	return 0;
}

感想:hackもぐもぐ