naoya_t@topcoder

SRM377 Div1 Easy: SquaresInsideLattice

過去問, 練習 | 23:39 |

8'35''ぐらい。

数が合わないと思って少し悩んでいたらiではなくwを使っていた。orz

Passed System Test / 229.22点

class SquaresInsideLattice {
 public:
  long long howMany(int width, int height) {
    int w=min(width,height);
    long long sigma=0;
    for(int i=1;i<=w;i++){
      sigma += (1LL+width-i)*(1LL+height-i)*i;
    }
    return sigma;
  }
};

SRM378 Div1 Easy: TrueStatements

過去問, 練習 | 23:11 |

思いついたのをまっすぐ書いた。3'45''ぐらい。

Passed System Test / 244.98点。

#include <vector>
#include <queue>
using namespace std;
#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++)

class TrueStatements {
 public:
  int numberTrue(vector<int> stmts) {
    vector<int> cnt(51,0);
    tr(stmts,it) cnt[*it]++;
    priority_queue<int> pq;
    rep(i,51){
      if(cnt[i]==i) pq.push(i);
    }
    return pq.empty()? -1: pq.top();
  }
};

priority_queueを有意義に使えて気持ちいい。

SRM379 Div1 Easy: SellingProducts

過去問, 練習 | 22:39 |

サンプルケースが親切

#define sz(a)  int((a).size())
#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++)

class SellingProducts {
 public:
  int optimalPrice(vector<int> price, vector<int> cost) {
	int n=sz(price);
    vector<pair<int,int> > pc(n);
    rep(i,n){ pc[i]=make_pair(price[i],cost[i]);}
    sort(all(pc));
    int summax=0, the_price=0;
    rep(i,n){
      int p=pc[i].first;
      int sum=0;
      for(int j=i;j<n;j++){
        int d=(p - pc[j].second);
        if(d>0) sum+=d;
      }
      if(sum>0){
        if(sum==summax) ;
        if(sum>summax){
          summax=sum;
          the_price=p;
        }
      }
    }
    return the_price;
  }
};

いきなりコーディングしてるけどちゃんとまとめてからにした方がいい。却って時間をロスしている。(199.45点だったか)

SRM432 Div1 Medium: GroupedWord

過去問, 練習 | 21:21 |

昨日のSRMの500点問題を解いてみる。

#define sz(a)  int((a).size())
#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 lastc(str) (*((str).end()-1))

typedef long long ll;
typedef vector<int> vi;

class GroupedWord {
  int n;
  vs ps;
  vi chs;

  pair<int,string> sub(const string &str, int len, ll av, ll chs_used){
    if(len==n) return make_pair(1,str);
    if(av==0LL) return make_pair(0,"");
    pair<int,string> p=make_pair(0,"");
    int last = sz(str)>0 ? lastc(str) : -1;
    for(ll i=0,mi=1LL;i<n;i++,mi<<=1){
      if(!(av&mi)) continue;
      ll dub=chs[i]&chs_used;
      if(ps[i][0]==last) dub-=(1LL<<(last-'a'));
      if(dub) continue;
      int ilast = lastc(ps[i]);
      ll av_new=av-mi, chs_new=chs_used|chs[i];
      for(ll j=0,mj=1LL;j<n;j++,mj<<=1){
        //if(j==i)continue;
        if((av_new&mj)==0) continue;
        if((chs_new&chs[j])==0) continue;
        if(ilast==ps[j][0]) continue;
        av_new-=mj;
      }
      pair<int,string> s=sub(str+ps[i],len+1,av_new,chs_new);
      if(p.first + s.first >= 2) {
        if(p.second!=s.second) return make_pair(2,"MANY");
      }
      if(s.first>0) p=s;
    }
    return p;
  }
  ll used_chars(const string &s){
    ll m=0LL;
    rep(i,sz(s)){
      ll mi=1LL<<(s[i]-'a');
      if((m&mi) && (i>0 && s[i-1]!=s[i])) return -1;
      m |= mi;
    }
    return m;
  }
 public:
  string restore(vector<string> parts) {
    n=sz(parts);
    ps=parts;
    chs.resize(n);
    rep(i,n) if((chs[i]=used_chars(parts[i]))<0) return "IMPOSSIBLE";
    pair<int,string> result = sub("", 0, (1LL<<n)-1LL, 0LL);
    switch(result.first){
      case 0: return "IMPOSSIBLE";
      case 1: return result.second;
      default: return "MANY";
    }
  }
};

TLE。

メモ化バージョンを作ってみたがローカルで28秒（おそらくサーバだと8〜10秒程度）かかるケース(#27)がある。

INPUT: {{"fffff", "hggggggg", "fh", "hhh", "ddde", "ddddd", "cccccc", "ccccoo", "oooodd", "cccccc", "ooooooo", "oo", "eeeeeeeee", "ee", "ddddddd", "ggggggg", "fff"}}
EXPECTED: "MANY"

後でまた考えよう。