そろそろ1000点問題などもやりはじめる。

FanFailure

class FanFailure {
public:
  vector <int> getRange(vector <int> capacities, int minCooling) {
    int mfs=capacities.size();
    int mfc=capacities.size();
    vector <int> result;
    sort(capacities.rbegin(),capacities.rend());
    int rest = minCooling;
    for(int i = 0;i<capacities.size();++i) {
      rest -= capacities[i];
      mfs--;
      if (rest < 0) break;
    }

    sort(capacities.begin(),capacities.end());
    rest = minCooling;
    for(int i = 0;i<capacities.size();++i) {
      rest -= capacities[i];
      mfc--;
      if (rest < 0) break;
    }

特にこれといってはまるところはなし。

ChangePurse

class ChangePurse {
  int find_pos(vector <int> cointypes, int val){
    for(int i =0; i<cointypes.size();++i){
      if(val == cointypes[i]) return i;
    }
  }
public:
  vector <int> optimalCoins(vector <int> coinTypes, int value) {
    vector <int> cs = coinTypes;
    vector <int> mapped;
    vector <int> coins;
    vector <int> results;
    int num; 
    for(int i=0;i<coinTypes.size();++i) results.push_back(0);
    sort(cs.rbegin(),cs.rend());
    for(int k=0;k<cs.size();++k) mapped.push_back(find_pos(coinTypes,cs[k]));

    for(int j =0;j<cs.size();++j){
      if((value+1)%cs[j]==0){
    coins.push_back(value / cs[j]);
    value = cs[j]-1;
      }
      else {
    coins.push_back(0);
      }
    }
    coins.push_back(value);
    for(int z = 0;z<cs.size();++z) results[mapped[z]] = coins[z];
    return results;
  }

    result.push_back(mfs);
    result.push_back(mfc);
    return result;
  }

ベクタをソートする際にソート前のインデックスを覚えておきたい場合どうやるのがいいのかがわからん。

InfiniteSequence

普通にメモ化するだけでいいのかなー、落とし穴でもあるんじゃなかろうか？なんて思ってたけどそんなものはなかった。

class InfiniteSequence {
  map<long long, long long> cache;
  long long acalc (long long n, int p, int q) {
    if (n == 0) return 1;
    if (cache.find(n) == cache.end()) {
      cache[n] = acalc(n/p, p, q) + acalc(n/q, p, q);
    }
    return cache[n];
  }
public:
  long long calc(long long n, int p, int q) {
    cache.clear();
    return acalc(n,p,q);
}
};

最初手元のテストが通らなくて悩んでいたらキャッシュをクリアーしてなかった。

cache.clear()

覚えた。

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をまわさない。

ここ何日か早起きしてはopenbabelのソースコード読んでた。

一通り読んだ。

C++クックブック
D. Ryan Stephens,Christopher Diggins,Jonathan Turkanis,Jeff Cogswell
オライリー・ジャパン / ￥ 4,515 ()
通常24時間以内に発送

が、3章の文字列処理ぐらいしかちゃんと理解できてないような。まぁ、クックブックなので参照したい時にひいて、理解を深める本なので、大体どういう事が書いてあるかをざっと掴んでおけばいい気もするけど。

読んで学ぶために買うならロベールか。

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

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点問題も解いていくか。

modfを使うやり方。

double i,d;
d = modf(32.654, &i);
cout << "int: " << i << endl;
cout << "double: " << d << endl;

stringstreamを使ってint型の変数に流し込むと残りが小数部分になる。

double d;
int i;
stringstream ss;
ss << 32.654;
ss >> i >> d;

整数部分がパカッとはがれる感じ?