たにたにのとくになにもせずだらだらするブログ:SRM482 Div2

2010年09月16日

SRM482 Div2

今回は500pできそうだったのにっ！

275p AverageAverage　229.58p

与えられた配列の「部分配列における平均」の平均を求める問題。気づいたら一発。

メモ用紙に平均出す式書いて式変形したら・・・あらふしぎ元の平均とおんなじじゃーん。というわけで相当時間無駄にしてしまったorz

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
class AverageAverage {
public:
    double average(vector <int> nl) {
        double sum=(double)accumulate(nl.begin(),nl.end(),0);
        return sum/nl.size();
    }
};

500p LockersDivTwo　(Compiled)

1からN番目までのロッカーを道を作りながら順番に開けていく問題。このときn番目の道は開いていないn+1番目のロッカーを開けるようにつくる。

vectorに1からNまで格納して要素が1個になるまで消していけばいい。ここでeraseを下手に使ったのが運のつき。イテレータに悩まされて結局提出できず。。。

消そうとするからいけないんだ！ということで消さない方をpush_backすればいいとはやく気づいていれば。

#include <iostream>
#include <vector>
using namespace std;
class LockersDivTwo {
public:
    int lastOpened(int N) {
        int turn=1;
        vector<int> a,b;
        for(int i=1;i<=N;++i) a.push_back(i);
        while(a.size()>1){
            turn++;
            b = a; a.clear();
            for(int i=0;i<b.size();++i)
                if(i%turn!=0) a.push_back(a[i]);
        }
        return a[0];
    }
};

消す方もあとで書いておきたいな。