れんしゅうちょう。

■ [GCJ]総評 20:33

OO|--|OX|--

1:39:26で31pts、925位。

Tシャツゲットしたのは嬉しい。

Bは問題把握出来たのが終了20分前で、segtreeでも使うのかなと思いつつ書ききれなかった。

Dは未だに理解していない。

以下A,Cのソースとか。

ツイートする

■ Problem A. Airport Walkways 12:28

問題

英語が読みやすかった。

色んな速さの動く歩道が(被らない場所に)あって、何も無い区間もあって、動く歩道or普通の歩道を歩いたり走ったりして、どこで走れば効率いいの？的な問題。

普通の歩道は速さ0で動く歩道として問題無い。

明らかに遅い所で走るのが得策。

あとはなんか適当にやってやるだけ。

x,s,r,t,n=getia
res = 0
ws = []
n.times do
    b,e,w = getia
    ws.push [w,e-b.to_f]
    x -= e-b.to_f
end
ws.push [0,x]
ws.sort_by!{|a|a[0]}

res = 0
ws.map! do |w|
    speed = w[0]
    length = w[1]
    if length / (speed + r) <= t
        t -= length / (speed + r)
        res += length / (speed + r)
    elsif t != 0
        length -= t * (speed + r)
        res += t
        res += length / (speed+s).to_f
        t = 0
    else
        res += length / (speed+s).to_f
    end
end
res

解法はぱっと思い付いたのに、e-b+1とかしてたり、走ってる時の速度がr+wだと勘違いしたりして、かなり手間取ってしまった。

to_fの場所がまちまちで怖いし、幾つかもっと綺麗に書けそうな場所があるけど、まぁACしたのでいいか。

ツイートする

■ 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位は無理だったので、まぁ。

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

ツイートする