kmjp's blog

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

New Year Contest 2015 : A - 2015、B - 鏡餅

NYC2015に参加。
中盤手間取って順位を落とすも、終盤で中堅どころの問題を3問解いてそこそこの順位。
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_1
http://nyc2015.contest.atcoder.jp/tasks/nyc2015_2

A - 2015

整数Nが与えられる。
Nを2進数表記するとき、leading zeroを抜いた表記が回文となるか答えよ。

愚直に文字列化して回文判定すればよい。

void solve() {
	int i,j,k,l,r,x,y; string s;
	ll N;
	cin>>N;
	FOR(i,60) {
		if(N&(1LL<<i)) s+='1';
		else s+='0';
	}
	while(s[s.size()-1]=='0') s=s.substr(0,s.size()-1);
	FOR(i,s.size()) {
		if(s[i]!=s[s.size()-1-i]) return _P("No\n");
	}
	_P("Yes\n");
}

B - 鏡餅

N個のお餅があり、それぞれのお餅はA[i]である。
このうち幾つかを縦に重ねたい。
その時、各お餅の上に乗る他の餅の総重量はそのお餅自身の重さ未満でなければならない。
最大何段までお餅を重ねられるか。

お餅を軽い順にチェックし、下に置けるものを貪欲に配置していけば良い。

int N;
ll A[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	ll tw=0;
	x=0;
	FOR(i,N) {
		if(A[i]>tw) {
			x++;
			tw+=A[i];
		}
	}
	cout<<x<<endl;
}

まとめ

ここらへんまでは簡単。