SRM541 Div.1

結果

o--(+0/-0) 149.02pts 310th(Div.1)
1629->1671(+42)

またもやhighest更新！

250

n匹(n<=50)のアリが格子点上を決まった方向に進む。
アリ同士が衝突すると消える。最終的に残るアリの数を答えよ。

はじめは任意の異なる2匹のアリがぶつかるかどうかが解るので時系列順に出して
云々かなぁと思ったもの、座標が-1000<=x,y<=1000と小さいのでシミュレーションでできるのでは
と思い書き始める。

2000秒シミュってやればよいので座標が同一なら消す、という作業をしてみると
sample2が合わないのでよく読むと、隣接する点から向かい合って進むと
その出会ったところで消えるようだ。おお気づいてよかった。

隣接してる場合を場合分けで書いてもなかなかsample合わないなぁと思っているところに
ああ0.5ずつやればいいのかと思いつく。0.5ならdoubleにしても誤差0だしとdouble配列に代入だけする

• >sample合う、提出。

    int countAnts(vector <int> xx, vector <int> yy, string direction) {
        int dx[4] = {1,0,-1,0};
        int dy[4] = {0,1,0,-1};
    
        int n=xx.size();
        bool vanished[n];
        int dir[51];
 
        double x[n];
        double y[n];
 
        for(int i=0;i<n;i++){
            x[i] = xx[i];
            y[i] = yy[i];
        }
 
        memset(vanished, false, sizeof(vanished));
        for(int i=0;i<direction.size();i++){
            if(direction[i] == 'E'){
                dir[i] = 0;
            }else if(direction[i] == 'N'){
                dir[i] = 1;
            }else if(direction[i] == 'W'){
                dir[i] = 2;
            }else{
                dir[i] = 3;
            }
        }
 
        for(int i=0;i<4002;i++){
            for(int j=0;j<n;j++){
                for(int k=j+1;k<n;k++){
                    if(x[j] == x[k] && 
                       y[j] == y[k]){
                        vanished[j] = true;
                        vanished[k] = true;
                    }
                }
            }
 
            for(int j=0;j<n;j++){
                if(!vanished[j]){
                    x[j] += 0.5*dx[dir[j]];
                    y[j] += 0.5*dy[dir[j]];
                }else{
                    x[j] = 2000;
                    y[j] = 2000;
                }
            }
        }
        int ret = 0;
        for(int i=0;i<n;i++){
            if(!vanished[i]) ret++;
        }
        return ret;
    }

500

わぁい X あかり X 大好き
f^k(S) = 2 * f^(k-1)(S) + hoge
だけどhogeの出し方がよくわからなかった。

challenge

250は長々とかいてる人が結構いて落とせるんだろうけど読む気がしない…
0.5ずつやってる人でシミュレーションを2000回しかしていない人を探したけどさすがにいなかった。

感想

黄色がちょっと長持ちしたのでうれしい。