ABCをそこそこの時間で解いて赤復帰。
http://codeforces.com/contest/587/problem/A
問題
N個の重りがある。各重りの重さは2^W[i]である。
Duffは1回で複数の重りを持ち上げられるが、その重さの合計は2の累乗でなければならない。
全重りを1回ずつ持ち上げるには、最低なんか重りを持ち上げればよいか。
解法
同じ重さの重りが2個あるなら、倍の重さの重りが1個あると考えても同じである。
よって、重りの合計を2進数表記して1の数を数えればよい。
int N; int W[1110101]; int ret; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>x, W[x]++; for(i=0;i<=1100000;i++) { W[i+1] += W[i]/2; if(W[i]%2) ret++; } cout<<ret<<endl; }
まとめ
ちょっと迷ったけどわかってしまえば簡単。