花火大会めもこんなものが・・・

    2010年07月29日

    SRM477 Div2

    SRM477おわりました。 ええ、オワリました。

    てかライブドアブログの使い方がよくわかりません。

    250p VacationTime

    あるわがままな王様と王妃がいてK日連続で休暇を取りたいとか勝手なことを言い出したので1~N日のうち一番会議の少ない期間を求めろという問題。

    N個の配列に会議の有無を入れて頭から順番にK個ずつ見て最小値出せば終わり。

    #include <vector>
    #include <algorithm>
    using namespace std;
    
    class VacationTime {
    public:
    	int bestSchedule(int N, int K, vector <int> workingDays) {
    		int result=N;
    		int task = workingDays.size();
    		vector<int> days(N,0);
    		vector<int> count(N-K+1,0);
    		for(int i=0;i<task;++i){
    			++days[workingDays[i]-1];
    		}
    		for(int i=0;i<N-K+1;++i){
    			for(int j=0;j<K;++j){
    				if(days[i+j]>0) ++count[i];
    			}
    		}
    		for(int i=0;i<N-K+1;++i)
    			if(count[i] < result) result = count[i];
    		return result;
    	}
    };
    

    500p Islands

    次はある島国の海岸線を測る問題。

    端の処理が面倒だけど、kingdomをすべて回して境界線を数えるだけ。

    今回は500もいけたかな・・・と思ったら偶奇間違えてたり・・・

    (時間内にギリギリ間に合わなかったのでちょっとだけ修正。)

    class Islands {
    public:
    	int beachLength(vector <string> kingdom) {
    		const int r[] = {1,0,-1,-1,0,1};
    		const int c[2][6] = {{0,1,0,-1,-1,-1},{1,1,1,0,-1,0}};
    		int R=kingdom.size(),C=kingdom[0].size();
    		int result=0;
    		for(int i=0;i<R;++i){
    			for(int j=0;j<C;++j){
    				if(kingdom[i][j] == '.') continue;
    				if(i!=R-1 && (j!=C-1||(j==C-1&&i%2==0)) && kingdom[i+r[0]][j+c[i&1][0]]=='.') ++result;
    				if(j!=C-1 && kingdom[i+r[1]][j+c[i&1][1]]=='.') ++result;
    				if(i!=0 && (j!=C-1||(j==C-1&&i%2==0)) && kingdom[i+r[2]][j+c[i&1][2]]=='.') ++result; 
    				if(i!=0 && (j!=0||(j==0&&i%2==1)) && kingdom[i+r[3]][j+c[i&1][3]]=='.') ++result;
    				if(j!=0 && kingdom[i+r[4]][j+c[i&1][4]]=='.') ++result;
    				if(i!=R-1 && (j!=0||(j==0&&i%2==1)) && kingdom[i+r[5]][j+c[i&1][5]]=='.') ++result;
    			}
    		}
    		return result;
    	}
    };
    


    tanitanin at 02:20│Comments(0)TrackBack(0) TopCoder | プログラミング

    トラックバックURL

    コメントする

    名前
     
      絵文字
     
     
    花火大会めもこんなものが・・・