naoya_t@topcoder

SRM383 Div1 Easy: Planks

過去問, 練習 | 23:55 |

Plankとは厚い板のこと。

vector<int>のなかから最大値を取るのに *max_element(all(lengths)) を使ってるけど、lengths.max()みたいなのって出来ないかな・・・

それにしてもサンプルケースが親切！

class Planks {
 public:
  int makeSimilar(vector<int> lengths, int costPerCut, int woodValue) {
    int n=sz(lengths); //1-50; 1-10000 each
    int maxl=*max_element(all(lengths)); // max length
    int maxa=0; // max amount
    for(int u=1;u<=maxl;u++){
      int cost=0, value=0;
      rep(i,n){
        int li=lengths[i];
        int k=li/u, r=li%u, cut=r>0?k:(k-1);
        int c=costPerCut*cut, v=k*u*woodValue;
        if (c<v) {
          cost+=c; value+=v;
        }
      }
      int a=value-cost;
      maxa=max(a,maxa);
    }
    return maxa;
  }
};

SRM384 Div1 Easy: Library

過去問, 練習 | 23:39 |

簡単。split()は自前

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

class Library {
 public:
  int documentAccess(vector<string> records, vector<string> userGroups, vector<string> roomRights) {
    map<string,int> ug, rr;
    int Nug=sz(userGroups), Nrr=sz(roomRights);
    rep(i,Nug) ug[userGroups[i]] = i; 
    rep(i,Nrr) rr[roomRights[i]] = i;

    set<string> books;
    tr(records,it){
      vector<string> rec = split(*it);
      if (!found(ug,rec[2])) continue;
      if (!found(rr,rec[1])) continue;
      books.insert(rec[0]);
    }
    return books.size();
  }
};

SRM385 Div1 Easy: UnderscoreJustification

過去問, 練習 | 23:10 |

これは速解き系なんだろうな。

最近、慣れてきたのかコードが汚くなってきた。（スペースの数が減ったりとか）

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())

class UnderscoreJustification {
 public:
  string justifyLine(vector<string> words, int width) {
    int n=words.size(), gaps=n-1, len=0;
    tr(words,it)len+=it->length();
    int minspaces=len+gaps, ds=width-minspaces, dsall=1+ds/gaps,dsr=ds%gaps;
    int cn=1<<gaps;
    vector<string> candidates(cn,"");
    rep(i,cn) {
      if(__builtin_popcount(i)!=dsr) continue;
      stringstream ss;
      ss << words[0];
      for(int j=1,b=1;j<=gaps;j++,b<<=1){
        string s_(dsall+((i&b)?1:0), '_'); // dsall+ の後の括弧がなくて結果が短くなるのでおかしいなと暫く悩んだ
        ss << s_ << words[j];
      }
      candidates[i] = ss.str();
    }
    remove_(candidates,"");
    sort(all(candidates));
    return candidates[0];
  }
};

SRM386 Div1 Easy: CandidateKeys

過去問, 練習 | 17:52 |

(statistics)

問題の意味がなかなか掴めなくて悩む。

サンプルのTest Caseは通るけどシステムテストが通らない←いまここ

後でやり直そう。

class CandidateKeys {
  string mask(string orig, int m){
    char buf[11];
    int j=0;
    rep(i,orig.length()) {
      if (m==0) break;
      if (m&1) buf[j++] = orig[i];
      m/=2;
    }
    buf[j]=0;
    string s = buf;
    return s;
  }
 public:
  vector<int> getKeys(vector<string> table) {
    vector<int> ans;
    int smallest=INT_MAX, largest=0;

    int l=table[0].length();
    set<string> ts(all(table));
    int n=sz(ts); // <2-50, 1-10
    if (n==1) return ans;

    vector<int> superkeys;
    set<int> candidate_keys;
    int pmax = (1<<l)-1;
    for (int p=1;p<=pmax;p++) {
      set<string> s;
      tr(ts,it){
        s.insert(mask(*it,p));
      }
      if (sz(s)==sz(ts)) superkeys.pb(p);
    }
    for(int i=0,c=sz(superkeys); i<c; i++) {
      int pi=superkeys[i];
      int cnt=0;
      for(int j=0; j<i; j++) {
        if (i==j) continue;
        int pj=superkeys[j];
        if ((pi & pj) == pj) cnt++;
      }
      if (cnt==0) candidate_keys.insert(__builtin_popcount(pi));
    }
    if (sz(candidate_keys)==0) return ans;

    tr(candidate_keys,it){
      if(*it <smallest) smallest=*it;
      if(*it >largest) largest=*it;
    }
    ans.pb(smallest); ans.pb(largest); return ans;
  }
};