naoya_t@topcoder

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

過去問マラソン | 15:18 |

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

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の倍数であること
  • 九つの数から３つを選ぶ組み合わせのうち、３数を足すと総和の1/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: どの３数が使われているか（マスク）
    // この３組をそれぞれ何行目に使うか・・・６通り
    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[マスク] = ３数の組み合わせ６パターン(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); // ３数３組の合計(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);
  }
};