SRM543 Div.1

結果

o--(+0/-0) 232.13pts(192nd)
1705->1768(+63)
またもやhighest更新です。

Petrとはじめて同部屋でした。

250

各bitごとに調べていった。
下から[a,b]のxorを取ったときの下からkbit(0-indexed)目は

(([0,b]の下からkbit目が1の個数)-([0,a-1]の下からkbit目が1の個数))%2

で求まるので、これを計算すればよい。
下からkbit目は明らかに2^(k+1)周期で、(2^k)-1までが0、それ以降が1という並びになっているので、
それを計算すればいい。
一応最大ケースぐらい調べてからsubmit。

mod 4とるともっと簡単にできたらしい。知らなかった。

ソースはこちら

500

思いついたけど時間足りなくて、practiceで通しました。
川は全て横に渡って、最後に上にあがるとすると

sum(width[i]/speed[i]) + length / walk

で辿りつけるので、どういうときに川を渡るときに上に行けばいいか考えてみる。
縦10^5で横50だからDPかなぁと思うも、2回目以降の横断はどこから来たかも考えないといけないので
結局O(10^10)以上になるっぽいので断念。

結局合計で縦にlength上がらないといけないので、1上に上がるコストの小さい順にgreedyに
取っていけばいいんじゃないか、思い小さいサンプル用に書いてみる->どうやらそのようである。

ここから、要素数50なので毎回計算すりゃいいのに、priority_queue?とか思ってハマった。
あとは10^10のオーバーフローに注意…途中でsqrt(10^10)-> -nanになってるにも関らず精度の悪い答えが出てしまうのであれどっかで誤差死してる、とか勘違いしてしまった。

以下ソース

     double getMin(int length, int walk, vector <int> width, vector <int> speed) {
         int n = width.size();
         double cur[n], nxt[n], ret=0;
         int point[n];
         int walk_len=0;
         for(int i=0;i<n;i++){
             cur[i] = (double)width[i] / speed[i];
             nxt[i] = sqrt((double)width[i] * width[i] + 1) / speed[i];
             point[i] = 0;
         }

         for(int i=0;i<length;i++){
             double mini = 1.0 / walk;
             bool iswalk = true;
             int ind;
             for(int j=0;j<n;j++){
                 if(point[j] < length && mini > nxt[j] - cur[j]){
                     mini = nxt[j] - cur[j];
                     ind = j;
                     iswalk = false;
                 }
             }
             if(iswalk){
                 walk_len++;
             }else{
                 point[ind]++;
                 cur[ind] = nxt[ind];
                 nxt[ind] = (double)sqrt((double)width[ind] * width[ind] + (double)(point[ind]+1) * (point[ind]+1)) / speed[ind];
             }
         }
         
         for(int i=0;i<n;i++){
             ret += cur[i];
         }
         dump(walk_len);
         ret += (double)walk_len / walk;
         return ret;

     }

感想

そろそろ500も4回に1回ぐらい通せるようになりたいです。