Problem Statement for BirthdayReminders

素直に書いたら、タイムアウトで撃沈された。システムテストの３個目でも落とされる。

class BirthdayReminders {
public:
  vector <string> remind(vector <string> friendNames, vector <int> birthDates, int currentDate, vector <string> occasions, vector <int> days, int k) {
    vector <string> rem;
    vector <int> times;
    stringstream ss;

    int fs = friendNames.size();
    int os = occasions.size();
    for(int l=0;l<fs*os;l++) times.push_back(0); 

   for(int i=1;i<1000001;++i){
      for(int j=0;j<occasions.size();++j){
        for(int m=0;m<friendNames.size();++m){
          int n = m*os+j;
          if(i-birthDates[m]>0 && (i-birthDates[m])%days[j] == 0) {
            times[n]++;
            if(i >= currentDate) {
              ss << i << ". " << friendNames[m] << " " << occasions[j] << " (" << times[n] << ")";
              rem.push_back(ss.str());
            if(rem.size() == k) return rem;
              ss.str("");
              ss.clear();
            }
          }
        }
      }
    }
    return rem;
  }
};

最初にテーブルを作っておいて最小の日を探しつつ更新していく。

教訓:安直にforをまわさない。

indexが昇順になるように文字列を連結していってその長さを答える

最初はindexを増やしていきながらマッチする文字列領域を決めていくという流れでコードを書いたのだけどそれだとシステムテストが通せなかったので、あきらめた。

{"aaaaaaaaaa", "a", "ab", "a", "abbbb"}

が14でなくて16になってしまう。

結局マージしたい文字列がsuperstringに含まれるかfindして、見つかればインデックスを書き換えて次の文字をマージしていく。含まれない場合はオーバーラップしている部分を一文字ずつ減らしながら探っていく方法に変えた。

class OrderedSuperString {
public:
  int getLength(vector <string> words) {
    string superstring = words[0];
    int ind = 0;
    if(words.size() == 1) return superstring.length();

    for(int i=1;i<words.size();++i){
      int matched = superstring.find(words[i],ind);
      if(matched != string::npos){ 
        ind = matched; continue;
      }

      int overlapped; 
      for(overlapped=min(superstring.length()-ind,words[i].length());overlapped>0;--overlapped){
        if(superstring.substr(superstring.length()-overlapped,overlapped) == words[i].substr(0,overlapped)) break;
      }
      ind = superstring.length()-overlapped;
      superstring += words[i].substr(overlapped,words[i].length()-overlapped);
    }
    return superstring.length();
  }
};

文字当て

countメソッドを覚えたのでメモ。

class Hangman {
public:
  string guessWord(string feedback, vector <string> words) {
    vector <string> candidates;

    for(int i=0;i<words.size();i++) {
      if(words[i].length() == feedback.length()) {
    vector <char> used,fused;
    int mismatched =0;
    for(int j=0;j<feedback.length();j++) {
      if(feedback[j] != '-' && feedback[j] != words[i][j]) {
        mismatched++;
      }
      else if (feedback[j] != '-' && feedback[j] == words[i][j]) {
        int fc = (int) count(feedback.begin(), feedback.end(), feedback[j]);
        int wc = (int) count(words[i].begin(), words[i].end(), feedback[j]);
        if (fc != wc) mismatched++;
      }
      }
      if(mismatched>0) continue;
        candidates.push_back(words[i]);
      }
    }
    if (candidates.size() == 1) return candidates[0];
    else return "";
  }
};

cutoffに合わせて丸める

  int round(string num, string cutoff) {
    stringstream ss,ss2;
    int i;
    double f,c;
    ss << num;
    ss >> f;
    ss2 << cutoff;
    ss2 >> c;
    i = int(f);
    if(f-i > c) i++;
    return i;
  }

それだけ

250点は縦横の合計が同じようになるように。３列のそれぞれの合計を比較して異なる数字のとこから入れるべき値を決定。

class MagicSquare {
public:
  int missing(vector <int> square) {
    int total[3] = {0,0,0};
    for(int i = 0;i<square.size();i++) total[i%3] +=square[i];
    if(total[0] == total[1]) return total[0] - total[2] - 1;
    if(total[0] == total[2]) return total[0] - total[1] - 1;
    if(total[2] == total[1]) return total[1] - total[0] - 1;
  }
 };

500点問題は小数点以下２桁を四捨五入したパーセントから、最小の母数を求める。母数を増やしながらパーセントを求めつつ四捨五入して比較。最初の正解が最小の母数。

class Percents {
public:
  int minSamples(string percent) {
    double pc;
    if(percent == "00.00%") return 1;
    stringstream ss;
    ss << percent;
    ss >> pc;
    for(int i=2;i<=10000;i++){
       for(int j=1;j<i;j++){
    double x = round(((double) j/i) * 10000) / 100;
      if(x == pc) return i;
      }
    }
    return 0;
  }
};

そろそろ1000点問題も解いていくか。

とりあえず一巡させると必ず一つはサラリーが求まるから、全部求まるまでループ。 他の人の解答見てmemsetの使い方を覚えた。

class CorporationSalary {
  long long  salary[50];
  bool isdetermind(int numbers){
    for(int i =0;i<numbers;i++) if(salary[i] == 0) return false;
    return true;
  }

public:
  long long totalSalary(vector <string> relations) {
    long long total = 0;
    int num = relations.size();
    for(int i=0;i<num;i++) salary[i] = 0; 
    //  memset(salary,0,sizeof(salary));

    int i = 0;
    while(!isdetermind(num)){
      i == num-1 ? i=0 : ++i;

      if( salary[i] > 0) continue;
      if(relations[i].find('Y') == string::npos) {
        salary[i] = 1;
        continue;
      }

      long long r = 0;
      int flag = 0;
      for(int j=0;j<relations[i].size();j++){
        if(relations[i][j] == 'Y') {
          salary[j] > 0  ? r += salary[j] : flag++;
        }
      }

      if(flag == 0) salary[i] = r;
    }

    for(int k=0;k<num;k++) total += salary[k];
    return total; 
  }
};

MarblesInABag

最初は再帰で考えて

class MarblesInABag {
  double gp(int rc, int bc){
    if(rc > bc) return (double) 0;
    if(rc == 0) return (double) 1;
    if(rc == 1 && bc == 0) return (double) 0;
    return (double) rc /(rc+bc) * gp(rc-1,bc-1) 
    + (double) bc/(rc+bc) * gp(rc, bc-2);
  }
public:
  double getProbability(int redCount, int blueCount) {
    return gp(redCount,blueCount);
  }
};

でこれをメモ化すればいいと思ってたんだけど、それだと、4000*4000の配列を用意しないといけないのでダメだということに気づいた。

というよりここがスタートでO(N^2)をO(N)にするというのが問題の意図だったらしい。

トップのヒトの解答をみると2*5000の配列にしていて赤が一個の時の確率から始まって赤の数を増やしながら、表を更新していた。

ここでのループで解く場合というやりかたになるのかな。

小数点の切り上げはceil

(int) ceil(pointNeed);

7段階評価の予測と実測のズレの頻度を求める。

using namespace std;
class IBEvaluator {
public:
  vector <int> getSummary(vector <int> predictedGrades, vector <int> actualGrades) {
    vector <int> diffGrades;
    vector <int> summary;

    int total = predictedGrades.size();

    for (int i=0;i<total;i++){
      diffGrades.push_back( abs(predictedGrades[i]-actualGrades[i]) );
    }

    for (int j=0;j<7;j++){
      int count = 0;
      for(int k=0;k<total;k++) if(diffGrades[k] == j) count++;
      summary.push_back( (int) (((double) count / total) * 100) );
    }
    return summary;
  }

最初からベクターの大きさがわかっている場合、最初に初期化しておいて

total[abs(predictedGrades[i]-actualGrades[i])]++;

と書けるという事を赤色のヒトの解答をみて知った。

任意の数の素数で割り切れない場合を工学的素数とする。任意の数が与えられたとき、最小の素数じゃない工学的素数を求めよ。

という問題。最大の素数の二乗が答えなんで、篩にかけるコードを書いて最大の素数を二乗すればいいだけだった。

ロベールもきた。

ロベールのC++入門講座
ロベール
毎日コミュニケーションズ / ￥ 3,990 ()
通常24時間以内に発送

週末ぐらいから読み始めたいが、、、、今朝mozart入れてしまったからCTMCPとどっちやろうか迷う。

コンピュータプログラミングの概念・技法・モデル(IT Architect' Archiveクラシックモダン・コンピューティング6) (IT Architects’Archive CLASSIC MODER)
セイフ・ハリディ,ピーター・ヴァン・ロイ,Peter Van-Roy,Seif Haridi
翔泳社 / ￥ 8,610 ()
通常24時間以内に発送

ちなみにMozartは

sudo port install mozart

ではいるのでラクチン。