Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-12-29

過去問マラソン(#6):SRM149

| 21:35 | 過去問マラソン(#6):SRM149 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(#6):SRM149 - naoya_t@topcoder 過去問マラソン(#6):SRM149 - naoya_t@topcoder のブックマークコメント

Easy(250): BigBurger

  • 夕食前にすこし時間があったので先にSRM149のEasyを解く。
  • 結果が0ばかり出ておかしいなーと思ってたらwait=arrival[i]-t って書いてたりとか
  • 5'20'', passed system test
  • もっと速く解きたい
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

class BigBurger {
 public:
  int maxWait(vector <int> arrival, vector <int> service) {
    int n=sz(arrival), t=0, waitmax=0;
    rep(i,n){
      if(t<arrival[i]) t=arrival[i];
      int wait=t-arrival[i]; waitmax=max(waitmax,wait);
      t+=service[i];
    }
    return waitmax;
  }
};

過去問マラソン(今日こそ#5):SRM148

| 15:18 | 過去問マラソン(今日こそ#5):SRM148 - naoya_t@topcoder を含むブックマーク はてなブックマーク - 過去問マラソン(今日こそ#5):SRM148 - naoya_t@topcoder 過去問マラソン(今日こそ#5):SRM148 - naoya_t@topcoder のブックマークコメント

昨日は戦闘環境再構築に時間を取られてしまったので気を取り直して5日目。

Easy(250): CircleGame

  • カードの文字から数値への変換に
  • 11'31''...だらだら時間かけすぎ
    • 動画音声聞きながらとか駄目だなw
  • systest一発
using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)

class CircleGame {
  int tonum(char c){
    switch(c){
      case 'A': return 1;
      case 'T': return 10; 
      case 'J': return 11;
      case 'Q': return 12;
      case 'K': return 13;
    }
    return (int)(c - '0');
 }
 public:
  int cardsLeft(string deck) {
    vector<int> dc;
    rep(i,sz(deck)) if(deck[i]!='K') dc.pb( tonum(deck[i]) );
    int n=sz(dc);
    while(1){
      int del=0;
      rep(i,n) { if (dc[i]<0) continue;
        FOR(df,1,n-1) {
          int j=(i+df)%n; if (dc[j]<0) continue;
          if (dc[i]+dc[j]==13) { dc[i]=dc[j]=-1; del++; }
          break;
        }
      }
      if (del==0) break;
    }
    int cnt=0;
    rep(i,n) if(dc[i]>0) cnt++;
    return cnt;
  }
};

もう一度。

  • 今度は削除カードをマーキングだけでなく本当に削除する。
  • 当然ながらこっちの方が考えやすい。
  • 9'0''. passed system test.
  • あとはタイピング速度。久しぶりにHHKB使っててまだ馴染まない…
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())

class CircleGame {
 public:
  int cardsLeft(string deck) {
    int tonum[128];
    rep(i,10) tonum['0'+i]=i;
    tonum['A']=1, tonum['T']=10, tonum['J']=11, tonum['Q']=12, tonum['K']=13;
    vector<int> dc;
    tr(deck,s){
      if(*s=='K') continue;
      dc.pb(tonum[*s]);
    }
    int del,left;
    do{
      del=0; left=sz(dc);
      rep(i,left){
        if(dc[i]+dc[(i+1)%left]==13) {
          dc[i]=dc[(i+1)%left]=-1;
          del++;
        }
      }
      remove_(dc,-1);
      left=sz(dc);
    } while(del>0);
    return left;
  }
};

tonum() は、strchr() あるいは index() を使っても書けますね

class CircleGame {
  int tonum(char c){
    const char *p="_A23456789TJQK";
    return strchr(p,c)-p; // strchrでもindexでも可
  }
 public:
  int cardsLeft(string deck) {
    vector<int> dc;
    tr(deck,s){
      int c = tonum(*s); if (c==13) continue;
      dc.pb(c);
    }
    ...
  }
};

Medium(450): MNS

  • 可能な魔法陣(斜めsumなし)全パターン数え上げ
    • 九つの数の総和が3の倍数であること
    • 九つの数から3つを選ぶ組み合わせのうち、3数を足すと総和の1/3になるものを全抽出
    • 3数の組を3つ選び、互いにかぶらないような組み合わせを全抽出
    • この組み合わせについて、縦横それぞれに並べ替え(6x6=36通り)、魔法陣になるパターンを探す。
  • 何度も使う順列組み合わせはできればメモ化
  • 42'2''
  • systest一発
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class MNS {
  map<int,set<int> > mm;
  set<int> pat;
  int goal;
  
  void sub(int m1,int m2,int m3){
    // mm[マスク] => 32進数×6つ
    tr(mm[m1],t1){
      tr(mm[m2],t2){
        tr(mm[m3],t3){
          if (*t1 + *t2 + *t3 == goal) {
            pat.insert((*t1 << 16) | *t2);
          }
        }
      }
    }
  }
  
  void check(int m1,int m2,int m3){
    // m1,m2,m3: どの3数が使われているか(マスク)
    // この3組をそれぞれ何行目に使うか・・・6通り
    sub(m1,m2,m3); sub(m1,m3,m2);
    sub(m2,m3,m1); sub(m2,m1,m3);
    sub(m3,m1,m2); sub(m3,m2,m1);
  }

 public:
  int combos(vector <int> numbers) {
    int sum=0; rep(i,9)sum+=numbers[i];
    if (sum%3) return 0;
    int th=sum/3;

    set<int> tri;

    mm.clear();
    // mm[マスク] = 3数の組み合わせ6パターン(32進表記)の集合
    FOR(i,0,6){
      FOR(j,i+1,7){
        FOR(k,j+1,8){
          int m = (1<<i) | (1<<j) | (1<<k);
          // m: 何番目の数を使ってるかを示すマスク
          int a=numbers[i], b=numbers[j], c=numbers[k];
          if (a+b+c == th) {
            tri.insert( m );
            set<int> s;
            s.insert((a<<10)|(b<<5)|c);
            s.insert((a<<10)|(c<<5)|b);
            s.insert((b<<10)|(c<<5)|a);
            s.insert((b<<10)|(a<<5)|c);
            s.insert((c<<10)|(a<<5)|b);
            s.insert((c<<10)|(b<<5)|a);
            mm[m] = s;
          }
        }
      }
    }

    pat.clear();
    goal = th*(1024+32+1); // 3数3組の合計(32進表記)

    vector<int> tv(all(tri)); // set => vector
    int n = sz(tv);
    FOR(i,0,n-3){
      FOR(j,i+1,n-2){
        if (tv[i]&tv[j]) continue;
        FOR(k,j+1,n-1){
          if (tv[k]&(tv[i]|tv[j])) continue;
          // 使ってる数がかぶってない組み合わせのみについて
          check(tv[i],tv[j],tv[k]);
        }
      }
    }
    
    return sz(pat);
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091229