Codeforces Round #320 (Div.2) [Bayan Thanks-Round] 参加記

codeforces

はい。 x----- (0/0) 1195(-68)
http://codeforces.com/contest/579
遂に灰に戻った。これが実力を真っ当に反映した値なのでしょう・・・

A. Raising Bacteria

ざっくりと大意

・最初は空の容器にバクテリアを1追加すると、次の日にはそれが倍に増えて2になっている。 ・バクテリアを5にしたい場合は1入れてから2->4と増えたあとに1追加で5になる。

方針のようなもの

・コンテスト時間中は何かあるだろうとは思いつつも全然解法に気づかなかったし、強引にDPっぽいの書いたのも入力の値が大きくなったりするとダメで通せなかった。。。

C++11

//テストケース3でランタイムエラーです。。
#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    double pai=3.141592653589;
    long long x;
    scanf("%lld",&x);
    vector<long long> dp(x);
    fill(dp.begin(),dp.end(),x);
    dp[x]=0;
    for(long long i=x;i>0;i--){
        if(i%2==0){
        dp[i/2]=min(dp[i/2],dp[i]);
        }else{
        dp[i/2]=min(dp[i/2],dp[i]+1);
        }
    }
    printf("%lld\n",dp[0]);
    return 0;
}

解法としてはDPとか全然必要なくてバクテリアの増え方？がビットシフトと同等のようなので、2進数にして1の個数がバクテリアを追加した回数になる。
なのでpythonだと、

python

print str(bin(int(raw_input()))).count('1')

とか1行で終わる。気づけなかったのは悔しい。。 B,C問題も一応は眺めたんですけどA問題で嵌って諦めて0完で終わりました。。