Hatena::Grouptopcoder

れんしゅうちょう。 このページをアンテナに追加 RSSフィード

 | 

2011-06-05Google Code Jam 2011 Round 2

Problem C. Expensive Dinner 12:28

問題

これも英語がわかりやすい問題。

降順と昇順で行くのかと一瞬思ったけど、サンプルからして違うっぽい。

10辺りまで解を見る為に、permutation全て試そうと思って、こんなん書く。

n = geti arr = (1..n).to_a
min = [Infinity]
max = [0]
arr.permutation.each do |k|
    c = 0
    tmp = 0
    pd = 1
    for i in k
        if c%i != 0 || c.zero?
            pd = pd.lcm(i)
            c += pd - c
            tmp += 1
        end
    end
    min = [[tmp,k.dup],min].min
    max = [[tmp,k.dup],max].max
end
p [min,max]
max[0] - min[0]

作りながら、lcm使ってるって事は素数のn乗とかを全部やりゃいいんじゃないかとか考えて、適当に書いたらサンプル通った。

ex)N=10

min:9,8,7,5,その他(LCM(9,8,7,5)は10以下の全てで割り切れる)

max:1,2,4,8,3,9,5,7,その他

よってminは素数の個数、maxは素数のn乗の個数的な。

def primeN(n)
    flg = []
    primePowerList = []
    resA = [0,1]
    cnt = 0
    for i in 2..n
        if flg[i].nil?
            flg[i] = true
            cnt += 1
            ii = i * i
            while ii <= n
                flg[ii] = false
                ii += i
            end
            ii = i
            while ii <= n
                primePowerList.push ii
                ii *= i
            end
        end
        resA[i] = cnt
    end
    primePowerList.sort!
    resB = [0,1]
    tmp = 1
    for i in 2..n
        if primePowerList[tmp] == i
            tmp += 1
        end
        resB[i] = tmp+1
    end
    [resA,resB]
end
$pn,$ppn = primeN(10000)
gcj_loop do
    n = geti
    $ppn[n] - $pn[n]
end

投げてsmallAC.

明らかにLargeはオーダー的に通らないので、適当に書きすぎたのを修正しつつ、速度的に不安なのでC++に移行。

bool primef[1000020];
vector<int> plist;
void initialize(){
    ll max = 1000010;
    rep(i,max)primef[i]=true;
    primef[0]=primef[1]=false;
    int hoge = sqrt(max);
    for(ll i = 2; i <= hoge; ++i){ //ここ。ここさえ・・・
        if(primef[i]){
            plist.pb(i);
            ll ii = i * i;
            while(ii <= max){
                primef[ii] = false;
                ii += i;
            }
        }
    }
}
ll n;
ll Ipow(ll a,ll e){
    ll res = 1;
    while(e){
        if(e&1)res *= a;
        a *= a;
        e >>= 1;
    }
    return res;
}
void gcj_main(ostream &out){
    cin>>n;
    ll sq = sqrt(n);
    ll res = 0;
    foreach(p,plist){
        if(*p > sq)break;
        ll a = (ll)(log(n) / log(*p));
        if(Ipow(*p,a+1)==n)a+=1;
        //cout<<*p<<" :"<<a<<endl;
        res += a - 1;
    }
    if(n == 1)
        out<<0<<endl;
    else
        out<<res+1<<endl;
}

なんか出力小さいなぁと思いつつ投げる。コンテスト終了後WA

素数リスト求めるのになんでsqrt(max)までしかやってないのかと100万回問い詰めたい。

素数フラグならいいけど、リスト作ってんだろうが・・・

//の所のhogeをmaxにしたら通った。

多分素数^n(n>=2)のリスト作ってソートして二分探索すれば速くなるけど、max入力で大丈夫だったのでそのまんま。

もしLarge通せていても時間的に500位は無理だったので、まぁ。

しかし、こういうミスは無くしたいなぁ・・・

 |