SRM481

• SRM481
  • 250 お店をぐるぐるまわって何個の品物を買えるか。簡単な実装問題、のはずが結構はまった。
  • 500 論理パズルっぽい問題。oracleが居て、n人に卵が先か鶏が先か真実を告げるが、どちらなのか、神父が嘘をついているのか、どちらもありうるのかを判断する問題。900を先にやってこっちのデバッグでタイムアップしました。
  • 900 比較的簡単。しかし調子に乗りすぎて大して考えもせず特攻、Failed System Test. もう駄目だ。

Result

250: Passed System Test
500: Compiled
900: Failed System Test
レーティング下がったね。

Code

250

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<complex>

using namespace std;

class CircleMarket {
public:
  int makePurchases(vector <int> openTime, vector <int> closeTime, int travelTime) {
    int ret = 0;
    int now = 0;
    int tmax = 0;
    bool vis[101]={false,};
    
    for(int i = 0; i < closeTime.size(); ++i){
      tmax = max( tmax, closeTime[i] );
    }
    for(int i = 0; i < openTime.size(); ++i){
      
      //cout << i << " : " <<  openTime[i] << ' ' << closeTime[i] << " : "<<vis[i] << endl;
      if( openTime[i] <= now && now <= closeTime[i] && !vis[i] ){
	++ret;
	
	vis[i]=true;
	now += travelTime;
      }else{
	now += travelTime;
      }
      
      if( now > tmax ) break;
      if( i == openTime.size() - 1 ) i = -1;
      if( ret == openTime.size() ) break;
    }
    return ret;
  }
};

500

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<complex>

using namespace std;

class ChickenOracle {
public:
  string theTruth(int n, int eggCount, int lieCount, int liarCount) {
    int n_know_truth = n - lieCount;
    int n_donknow_truth = lieCount;
    int chikCount = n - eggCount;
    
    bool ambi=false;
    string ret = "The oracle is a lie";

    // cout <<" FIRST : " <<endl;
    for(int i = 0; i <= liarCount; ++i){
      if( eggCount - i < 0 ) continue;
      if( chikCount - (liarCount-i) < 0 ) continue;

      int consider_egg = eggCount - i + (liarCount - i );
      int consider_chik = chikCount + i - (liarCount - i );
      // cout << " i = " << i << " CEGG : " << consider_egg << " CCHICKEN : " << consider_chik << endl;
      if( consider_egg < 0 || consider_egg > n || consider_chik < 0 || consider_chik > n ){
	continue;
      }
      if( n_donknow_truth == n_know_truth && n_know_truth == consider_egg ){
	ambi=true;
      }
      if( consider_egg == n_know_truth && consider_chik == n_donknow_truth ){
	if( ret == "The chicken" ){ambi=true;}
	else if( true ) ret = "The egg";
      }else if( consider_egg == n_donknow_truth && consider_chik == n_know_truth ){
	if( ret == "The egg" ){ ambi=true; }
	else if( true ) ret = "The chicken";
      }
    }
    
    // cout <<"SECOND : " << endl;
    for(int i = 0; i <= liarCount; ++i){
      if( eggCount - (liarCount - i ) < 0 ) continue;
      if( chikCount - i < 0 ) continue;
      int consider_egg = eggCount + i - (liarCount - i );
      int consider_chik = chikCount - i + (liarCount - i );
      // cout << " i = " << i << " CEGG : " << consider_egg << " CCHICKEN : "  << consider_chik << endl;
      if( consider_egg < 0 || consider_egg > n || consider_chik < 0 || consider_chik > n ){
	continue;
      }
      if( n_donknow_truth == n_know_truth && n_know_truth == consider_egg ){
	ambi=true;
      }
      if( consider_egg == n_know_truth && consider_chik == n_donknow_truth ){
	if( ret == "The chicken" ){ambi=true;} 
	else if(true) ret = "The egg";
      }else if( consider_egg == n_donknow_truth && consider_chik == n_know_truth ){
	if( ret == "The egg" ){ ambi=true; }
	else if(true) ret = "The chicken";
      }
    }
    
    if( ambi ) ret = "Ambiguous";
    return ret;
  }
};

むちゃくちゃ汚い。lieCountから、真実を知っている人と知らない人の人数を求めて、それから嘘をついている人間をEgg側にしたりChichken側にしたりしながら、つじつまが合うかどうか判断する(liarCount回ループを回す)。

900

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<complex>

using namespace std;
class BatchSystem {
public:
  class Job{
  public:
    long long int d;
    string n;
    int i;
    bool operator<(const Job &t)const{
      if( d==t.d ){if( i==t.i ){return n<t.n;}else return i<t.i;}else return d<t.d;
    }
  };
  vector <int> schedule(vector <int> dur, vector <string> user) {
    vector<int> ret(user.size());
    vector<long long int> duration(dur.begin(),dur.end());
    map<string, vector<int> > result;
    vector<Job> jobs;

    for(int i = 0; i < user.size(); ++i){
      result[user[i]].push_back( i );
    }
    for(int i = 0; i < user.size(); ++i){
      for(int j = i+1; j < user.size(); ++j){
	if( i != j ){
	  if( user[i] == user[j] ){
	    duration[i] += duration[j];
	    duration.erase( duration.begin() + j );
	    user.erase( user.begin() + j );
	    --i;break;
	  }
	}
      }
    }

    for(int i = 0; i < duration.size(); ++i){
      jobs.push_back(Job());
      jobs[i].d = duration[i];
      jobs[i].n = user[i];
      jobs[i].i = i;
    }
    set<Job> sjobs;
    for(int i = 0; i < jobs.size(); ++i){
      sjobs.insert( jobs[i] );
    }
    
    int n = 0;
    for(set<Job>::iterator its = sjobs.begin(); its != sjobs.end(); ++its){
      //cout << its->n << " duration : "  << its->d << " index : " << its->i << endl;
      
      //cout << result[its->n].size() << endl;
      for(int i = 0; i < result[its->n].size(); ++i){
	int ind = result[its->n][i];
	ret[n++] = ind;
      }
    }
    
    return ret;
  }
};

同じ人のジョブをまとめてからソートすればいい。

一応これらでPassed System Testとなった。