今日のtopcoder

pythonと同じ感覚で、ベキ乗を計算するのに

 results += 2 ** i

とかやってたみたいで、コンパイル時に

invalid type argument of 'unary *'

というエラーが出てきてたのだけど、型か?キャストか?なんてドはまりしたあげく時間を食いつぶして死亡。

ユーザー登録する際にIDがかぶったら数字のナンバリングをする

setの使い方を覚えた。

class UserName {
public:
  string newMember(vector <string> existingNames, string newName) {
    int n=1;
    set <string> s;
    for(int i=0;i<existingNames.size();++i){
      s.insert(existingNames[i]);
    }

    if(s.count(newName) == 0) return newName; 

    while(1){
      stringstream ss;
      ss << newName << n;
      if(s.count(ss.str()) == 0) return ss.str();
      n++;
    }
};

set便利

一問も解けなかった。というか250点に時間をかけすぎたうえに途中であきらめたのがよくなかった。

RestaurantManager

席が埋まっているかどうかを、何番目のグループがどの席に座っているかという情報をmapで持たせようとしてたのが間違い。単にどの席がいつまで埋まっているかという時間の情報をベクタに突っ込んでおいて新規客の到着時刻と照らし合わせればよいだけだった。

class RestaurantManager {
public:
  int allocateTables(vector <int> tables, vector <int> groupSizes, vector <int> arrivals, vector <int> departures) {
    vector <int> occupied;
    int away = 0,j;
    sort(tables.begin(),tables.end());
    for(int i=0;i<tables.size();++i) occupied.push_back(0);

    for(int i = 0;i<groupSizes.size();++i){
      for(j = 0;j<tables.size();++j){
        if(groupSizes[i] <= tables[j] && occupied[j] <= arrivals[i]){
          occupied[j] = departures[i];
          break;
        }
      }
      if(j == tables.size()) away += groupSizes[i];
   }
   return away;
  }
};

Embassy

あとで

WindowManager

class WindowManager {
public:
  vector <string> screen(int height, int width, vector <string> windows) {
    vector <string> result;
    stringstream ss;
    int lx,ly,rx,ry;
    char c;
    result.clear();
    string s;
    s.clear();
    s = "";
    //    cout << width << "," << height << endl;
    for(int a=0;a<width;++a) s += " ";
    for(int b=0;b<height;++b) result.push_back(s);

    for(int i = 0;i<windows.size();++i) {
      ss.str(windows[i]);
      ss >> ly >> lx >> ry >> rx >> c;
      rx += lx -1;
      ry += ly -1;

      for(int y=0;y<height;++y) {
    for(int x=0;x<width;++x) {
      if((x==lx && y==ly) ||(x==lx && y==ry) ||(x==rx && y==ly) ||(x==rx && y==ry)) {
        result[y][x] = '+';
      }
      else if(((x == lx)||(x == rx)) && (y > ly) && (y < ry)) {
        result[y][x] = '|';
      }
      else if(((y == ly)||(y == ry)) && (x >lx) && (x < rx)) {
        result[y][x] = '-';
      }
      else if((x >lx) && (x < rx) && (y > ly) && (y < ry)){
        result[y][x] = c;
      }
        }
      }
      ss.str("");
      ss.clear();
    }
    return result;
  } 
};

三角形の数を数える

パズルみたいな問題。上向きと下向きに分けて数えていけばOK

class TriangleCount {
public:
  int count(int N) {
    int result = 0;
    for(int i = 1;i<=N;++i){
      for (int j = i;j<=N;j++){
    result += j-i+1;
    int down = j - i + 1 -i;
    if ((down) > 0) result += down; 
      }
    }
    return result;
  }
};

赤と黒のチェッカーボードの赤い部分を数える

チェッカーボードの作り方がおかしいのに気づかず、テストがこける理由が分からなかった。

class RedSquare {
public:
  int countTheEmptyReds(int maxRank, int maxFile, vector <int> rank, vector <int> file) {
    int board[50][50];
    int result = 0;
    memset(board,0,sizeof(board));
    bool black;
    for(int   i=0; i<maxRank;++i) {
      if     (i == 0) {black  = true;}
      else if(board[i-1][maxFile-1]){black = true;}
      else {black = false;}
      for(int j=maxFile-1; j>=0; --j) {
    if(black){
      black = false;    
        }
        else{
          board[i][j] = 1;
          black = true;
        }
      }
    }

    for(int k=0;k<rank.size();++k) {
      int m = rank[k]-1;
      int n = file[k]-1;
      board[m][n] = 0;
    }

    for(int x = 0;x<maxRank;++x)
      for(int y = 0;y<maxFile;++y) 
result += board[x][y];

    return result;  
}
};

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

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