とりあえず一巡させると必ず一つはサラリーが求まるから、全部求まるまでループ。 他の人の解答見て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);

ロベールと共に過ごした、梅雨の週末。

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

900p超えだけど、読みやすいのですらすら進んだ。

が、13章以降はかなりの流し読みってことで。

もともとopenbabelのコードが読みたくて始めたC++の勉強だが、topcoderが面白くて癖になったりとか、boostpythonにも興味がわいたりとか思わぬ副産物としての成果もあった。

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

ではいるのでラクチン。

250点問題は再帰でさらっとかけた。

500点問題はできたと思ったのにシステムテストで落とされてた。あれれと思ってみてみると、しょうもないミス。

1000点問題は開いてみたけど、ちょっと手が動かず。

結局さらに落ちて灰色。

forを0から回したい時にレンジの都合で負になってしまう場合maxで評価するとよい

for(int i=max(0,k);i<vectors.length();i+)

ふむふむ。

500点問題

• 文字列から?以外の数字の位置を探る。
• そこから左と右にそれぞれ数字を埋めていく

という流れで。

差分をとって10足して、そのあと10の余りをとって、さらに '0'を足せばキャストしなくていい。

  for(j=k-1;j>-1;j--) a[i][j]=(a[i+1][j]-a[i][j+1]+10)%10+'0';

こんな感じ

灰色に落ちた。というか実力に見合った色かもしれん。

• 250: 問題をちゃんと理解してなくて撃沈
• 500: 素直にとけば良さげな問題だったが、なんかおかしな事になって終了
• 1000: unopened

500は後でちゃんと解く。