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

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;
	}
};