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

kmjp's blog

競技プログラミング参加記です

AtCoder ARC #046 : A - ゾロ目数、B - 石取り大作戦

Cまではサクサク解けたけどDが解けず。
http://arc046.contest.atcoder.jp/tasks/arc046_a
http://arc046.contest.atcoder.jp/tasks/arc046_

A - ゾロ目数

小さい順からN番目のゾロ目の整数を答えよ。

自分は無駄に愚直に総当たりして検索したけど、最初の9個は1~9、次の9個は11~99、次の9個は111~999…と考えれば簡単だったね。

int iszoro(ll a) {
	int b=a%10;
	while(a) {
		if(a%10!=b) return 0;
		a/=10;
	}
	return 1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>x;
	i=1;
	while(1) {
		if(iszoro(i)) {
			x--;
			if(x==0) return _P("%d\n",i);
		}
		i++;
	}
}

B - 石取り大作戦

N個の石から2人交互に石を取り除く。
1回で先手は1~A個、後手は1~B個取り除ける。
最後の石を取り除いた方が勝ち。
両者最適手を取った場合、勝者はどちらか。

  • 先手が初手で石を取りきれる(A≧N)なら先手必勝。
  • A==Bなら、定番テクでN%(A+1)がゼロなら後手、それ以外先手必勝。
  • それ以外はA,B多く取れる方が勝ち。これはA==Bの時に2人合計で(A+1)取るようにし続けるのと同じことを多く取れる方が行えばいいため。
ll N,A,B;

void win(int x) {
	if(x>0) _P("Takahashi\n");
	else _P("Aoki\n");
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	if(A>=N) win(1);
	else if(A==B) win(N%(A+1));
	else win(B<A);
	
}

まとめ

Aはなぜ愚直に面倒な回答をしてしまったのだ…。

広告を非表示にする