topcoder

naoya_t@topcoder

2009-05-18

SRM353 Div1 Easy: Glossary

過去問, 練習 | 14:19 |

以前に見たことがある気がする（おそらくSRM前の準備運動がてら開いてみた）

stringをlowercaseするのに悩むなんてヘタレすぎる
答えが合わないとおもったらスペースのパディングの数が１つ足りないとか
30分ぐらいかかってしまった
passed system test

string lowercase(const string &str){
  int n=sz(str);
  char s[20];
  rep(i,n) s[i]=tolower(str[i]);
  s[n] = 0;
  return s;
}

class Glossary {
 public:
  vector <string> buildGlossary(vector <string> items) {
    int n=sz(items);
    vector<vector<string> > a_m(2);
    rep(i,26){
      int side=i/13;
      bool f=false;
      vector<pair<string,string> > is;
      rep(j,n){
        int cap=items[j][0]; if (cap>='a') cap-=32;
        if(cap=='A'+i) { f=true; is.pb(make_pair(lowercase(items[j]),items[j])); }
      }
      if (f) {
        sort(all(is));
        char buf[20];
        buf[0]= 'A'+i; for(int k=1;k<19;k++) buf[k]=' '; buf[19]=0;
        a_m[side].pb(buf);
        a_m[side].pb("-------------------");
        tr(is,it) {
          sprintf(buf,"  %-17s",it->second.c_str());
          a_m[side].pb(buf);
        }
      }
    }

    vector<string> ans;
    int al=sz(a_m[0]), nl=sz(a_m[1]);
    for(int i=0;i<al;i++){
      if(i<nl){
        ans.pb(a_m[0][i] + "  " + a_m[1][i]);
      } else {
        ans.pb(a_m[0][i] + "                     ");
      }
    }
    for(int i=al;i<nl;i++){
      ans.pb("                     "+a_m[1][i]);
    }
    return ans;
  }
};

SRM354 Div1 Easy: DateFormat

過去問, 練習 | 13:42 |

300点問題。

split(), map_atoi()は自作
今回 join() を書いた。最初にdateList[]を結合する時と、最後に答えをスペース区切りで繋げる時の合計２回使ってる
210.82points (20'22''), passed system test

typedef vector<int> vi;
typedef vector<string> vs;
#define pb  push_back
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

string join(vector<string> strs, const string &delim="")
{
  int n=strs.size(); if (n==0) return "";
  stringstream ss;
  ss << strs[0];
  for(int i=1;i<n;i++) { ss << delim << strs[i]; }
  return ss.str();
}

class DateFormat {
 public:
  string fromEuropeanToUs(vector <string> dateList) {
    vs dates = split(join(dateList)); int n=sz(dates);
    vs mins(n), maxs(n);
    vi ds; int lastd=0;
    rep(i,n){
      vi ns=map_atoi(split(dates[i],'/'));
      if(ns[0]<ns[1]){ // xX
        if (ns[1]<=12) { // mD, dM
          int d1=ns[0]*100 + ns[1], d2=ns[1]*100+ns[0];
          if(lastd < d1) { ds.pb(d1); lastd = d1; }
          else if(lastd < d2) { ds.pb(d2); lastd = d2; }
          else return "";
        } else { // mD
          int d=ns[0]*100 + ns[1];
          if(lastd<d) { ds.pb(d); lastd = d; }
          else return "";
        }
      }else if(ns[0]==ns[1]) { // md, <=12
        int d=ns[0]*101;
        if(lastd<d) { ds.pb(d); lastd = d; }
        else return "";
      }else{ //Xx
        if (ns[0]<=12) { // Md, Dm
          int d1=ns[1]*100 + ns[0], d2=ns[0]*100+ns[1];
          if(lastd < d1) { ds.pb(d1); lastd = d1; }
          else if(lastd < d2) { ds.pb(d2); lastd = d2; }
          else return "";
        } else { // Dm
          int d=ns[1]*100 + ns[0];
          if(lastd<d) { ds.pb(d); lastd = d; }
          else return "";
        }
      }
    }
    vs anss;
    rep(i,n){
      char buf[6];
      sprintf(buf,"%02d/%02d",ds[i]/100,ds[i]%100);
      anss.pb(buf);
    }
    return join(anss," ");
  }
};

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090518