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

問題を正確に読めるようになりたいです。

250p MicrowaveSelling　×

minPrice以上maxPrice以下のなるべく多く9が後ろについた値段でレンジ？を売りたいという問題。単に9が多く付けばいいと勘違いしてFailed System Test。

#include <iostream>
using namespace std;
class MicrowaveSelling {
public:
    int mostAttractivePrice(int minPrice, int maxPrice) {
        int r = minPrice, res = r, m = 0;
        while(r <= maxPrice){
            int t = r, cnt = 0;
            while(t%10==9){ // 最後から連続で9
                cnt++;
                t/=10;
            }
            if(cnt>=m){
                m=cnt;
                res=r;
            }
            r++;
        }
        return res;
    }
};

500p AfraidOfEven　×

N個からなる数列に対して偶数がキライな少年が偶数を2で可能な限り割ってしまうので、元の数列を答える問題。

1000p RectangleAvoidingColoringEasy　×

N×Mの板に白黒に色が塗ってあり、どの4点からなる長方形をとっても必ず1つ以上白と黒があるときrectangle-avoidingという。板には塗っていない部分もあり、これを白黒どちらかに塗ってrectangle-avoidingになる塗り方が何通りかを求める問題。

Challenge Phase　50p×2

250p問題の自分と同じミスしてる人を2人撃墜。。。自分が間違ってちゃ元も子もないですが。。。

撃墜ゲーでした。そしてオワタ。

250p DigitHoles　228.09p

数字が8だったら穴が2個、0,4,6,9だったら穴が1個、他は0個で穴の数を数えていく簡単なお仕事。

点数が低いのは読解力不足です。

class DigitHoles {

public:

    int numHoles(int num) {

        int res=0;

        while(num>0){

            int c = num%10;

            if(c==8) res+=2;

            else if(c==0||c==4||c==6||c==9) res++;

            num/=10;

        }

        return res;

    }

};

500p MovieSeating　Challenge Succeeded

映画館でnumFriends人分の座席を同じ行または列で取る方法が何通りあるかを求める問題。nCr*r!を行と列についてそれぞれ計算する。

numFriends=1のケース忘れてた。あとで気づいてｵﾜﾀ＼(^o^)／

#include <iostream>

#include <string>

#include <vector>

using namespace std;

class MovieSeating {

public:

    long long getSeatings(int nf, vector <string> hall) {

        long long res=0;

        int r = hall.size(); int c = hall[0].size();

        if(nf>r&&nf>c) return 0;

        for(int i=0;i<r;++i){

            int cnt=0;

            for(int j=0;j<c;++j) if(hall[i][j]=='.') cnt++;

            long long s=1;

            for(int k=cnt;k>cnt-nf;--k) s*=k;

            res += s;

        }

        if(nf==1) return res; // ←後で書き加えた

        for(int i=0;i<c;++i){

            int cnt=0;

            for(int j=0;j<r;++j) if(hall[j][i]=='.') cnt++;

            long long s=1;

            for(int k=cnt;k>cnt-nf;--k) s*=k;

            res += s;

        }

        return res;

    }

};

1000p BestApproximationDiv2 Opened

与えられた少数をF = A / B ( 1 <= B < num, 0 <= A < B )の形で近似して、A / BとFの合っている桁数を出す問題。

解いたら載せます。

Challenge Phase

なんか500が部屋全員落ちてるんですけど・・・

900だれも解いてないんですけど・・・

な感じでまったくチャレンジせず。今回学んだこと：撃墜する勇気大事・コーナーケース大事

結果

○××→228.09+0.0+0.0=228.09

707→704　ちょっと下がったー

今回は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];
    }
};

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

900p BaseConfusion　Opened

Daveが14→112って書いてたのは理解。B進数に直してる感じっぽい。でもEarlがやってることがわからない・・・

後日解いたら追記しま。

challenge

頭がまったく働いていなかったので適当にやったらあえなく不発。-25

今回はSystemTestがゴタゴタで大変なことに。何回もシステムテストやりなおしてたけど何があったんだろう。

レーティングはちょっとだけ上がったけど、イマイチな感じ。

250p CircleMarket　172.52p

円形の市場を時計回りにまわって開店時間内にどれだけのアイテムを買うことができるかという問題。

問題のとおりにやったけど時間かけすぎた。

200p以上はとりたかったなぁ。。。実装力を身につけたいところ。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
class CircleMarket {
public:
    int makePurchases(vector <int> openTime, vector <int> closeTime, int travelTime) {
        int res=0,total=0;
        int n = openTime.size();
        vector<bool> vis(n,false);
        while(1){
            bool f=true;
            for(int i=0;i<n;++i){
                if(total>=openTime[i]&&total<=closeTime[i]&&!vis[i]){ res++; vis[i]=true; }
                if(total>closeTime[i]&&f) f=true; else f=false;
                total+=travelTime;
            }
            if(res>=n) break;
            if(f) break;
        }
        return res;
    }
};

500p ChickenOracle　(Compiled)

預言者が鶏と卵問題の答えをn人に教え、そのn人からの答えを元に預言を当てる問題。全体数、「卵」と答えた人の数、預言者が嘘を教えた人数、嘘をついた人数が与えられてるっと。

とりあえずlieCountとliarCountが0のときを分岐させてみて、それからliarがいるときとか考えようとしたけど結局うまくいかず。紙にベン図とか描いていろいろ考えて、lieCountとliarCoutとその共通部分で３重ループの作ったけどテストケース通せなくてオワタ。

やりなおして後で載せるっぽ。

900p BatchSystem　Unopened

解いていません。

challenge

今回もパス。コーナーケースとか考える余裕なかったので。。。

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

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