AtCoder ARC #039 : A - A - B problem、B - 高橋幼稚園

2分遅れて参加したため、BのFirst Acceptは取れず。
辛うじて全完。
http://arc039.contest.atcoder.jp/tasks/arc039_a
http://arc039.contest.atcoder.jp/tasks/arc039_b

A - A - B problem

2つの3桁の整数A,Bが与えられる。
A,Bどれかの桁を1つまで変更してよいとき、A-Bを最大化せよ。
ただし桁数が3にならない変更は不可である。

高々3桁なので総当たりすればよい。

int ok(int x,int y) {
	int d=0;
	if(x/100%10!=y/100%10) d++;
	if(x/10%10!=y/10%10) d++;
	if(x%10!=y%10) d++;
	return d<=1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int A,B;
	cin>>A>>B;
	
	int ma=A-B;
	for(int x=100;x<=999;x++) if(ok(A,x)) ma=max(ma,x-B);
	for(int x=100;x<=999;x++) if(ok(B,x)) ma=max(ma,A-x);
	cout<<ma<<endl;
}

B - 高橋幼稚園

N人にK個の飴を分ける。
その時、全員の飴の数の積を最大化するような分け方の組み合わせ数を答えよ。

• K≧Nの時
  • みんな均等に飴を分けるのがよく、(K%N)人はceil(K/N)、残りはfloor(K/N)個貰えるようにすればよい。
  • 1個多くもらえる人を通り選択すればよい。
• K＜Nの時
  • どう頑張っても積が0になるので、誰に何個与えても良い。
  • よって解は重複組み合わせで計算でき、となる。

ll N,K;

const int CN=4001;
ll C[CN][CN];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
	if(K>=N) {
		cout << C[N][K%N] << endl;
	}
	else {
		cout << C[N+K-1][K] <<endl;
	}
}

まとめ

Bは入力例3をちゃんと把握しないと間違えるね。
危ない危ない。