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

今回は、前回やっとレートがちょっとだけ回復したので今回も勢いに乗りたい感じ。

250p TheAirTripDivTwo

飛行機に与えられた燃料で何回飛行ができるかを答える問題。燃料とかICFPを思い出す。

単純に燃料がゼロになるまで引いていけばいいはず・・・だったのに。変にfuelをいじったりとかi-1を返すとか汚いコードに。結果213.90p

#include <iostream> 
#include <vector> 
using namespace std;
class TheAirTripDivTwo { 
public: 
  int find(vector <int> flights, int fuel) { 
    int i=0; 
    while(fuel>=0){ 
      fuel-=flights[i]; 
      ++i; 
      if(i>flights.size()) break; 
    } 
    return i-1; 
  }
};

根本的に直してPlacticeで投げてみたら247.16p。これくらいは速く書けないとなぁ。。。

#include <iostream> 
#include <vector> 
using namespace std;
class TheAirTripDivTwo {
public:
  int find(vector <int> fl, int f) {
    int i;
    for(i=0;i<fl.size();++i){
      f-=fl[i];
      if(f<0) break;
    }
    return i;
  }
};

500p TheCoffeeTimeDivTwo

飛行機の乗客全員にコーヒーかお茶を配って最速を目指すスピードトライアル。

7人分のコーヒーor茶を容易するのに47秒、1席移動するごとに1秒、渡すのに4秒かかるそうな。

後ろから足せばいいってことに気づくのが遅すぎた。。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
class TheCoffeeTimeDivTwo {
public:
  int find(int n, vector <int> tea) {
    sort(tea.begin(),tea.end(),greater<int>());
    vector<int> coffee;
    int k=0;
    for(int i=n;i>0;--i){
      if(k<tea.size()&&i==tea[k])++k;
      else coffee.push_back(i);
    }
    int time=n*4;
    for(int i=0;i<tea.size();i+=7){
      time+=47;
      time+=tea[i]*2;
    }
    for(int i=0;i<coffee.size();i+=7){
      time+=47;
      time+=coffee[i]*2;
    }
    return time;
  }
};

1000p TheBoardingDivTwo

まだ解いてません。

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