Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-05-02

TCO10 Qualification Round 1 (※ノーゲーム)

10:02 | TCO10 Qualification Round 1 (※ノーゲーム) - naoya_t@topcoder を含むブックマーク はてなブックマーク - TCO10 Qualification Round 1 (※ノーゲーム) - naoya_t@topcoder TCO10 Qualification Round 1 (※ノーゲーム) - naoya_t@topcoder のブックマークコメント

DIVlevel問題名競技中後でSystem Test通過率備考
- 250 DNAMatching 提出 - passed - -
- 500 Palindromize3 間に合わず - - - 0
- 1000 - - -

Easy(250): DNAMatching

  • DNAについて、左右反転してA⇔T,G⇔Cを交換したものを用意
  • お互いに比較し、マッチしてる組み合わせを辺としたグラフを考えたら隣接行列ができる
  • はて
  • 最大ノーペア数どうやって出したらいいんだ
  • ノートに書いて考える
  • とりあえずグラフでくっついてるものを島にして、各島から1ノードずつ代表を出せば最大ノーペアが出来るんじゃないか
  • union-findで
  • あれどうやって島の数数えるんだっけ
  • ごにょごにょ
  • できた!
  • あれsubmitできない。timeout...
  • twitter見てもみんなsubmitできないみたい
  • 一度ログアウトしてみる。あれ。ログインできない><
  • これはノーゲームですね
#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++)
#define found(s,e)  ((s).find(e)!=(s).end())

class DNAMatching {
  char ct(char c){
    switch(c){
      case 'A': return 'T';
      case 'T': return 'A';
      case 'C': return 'G';
      case 'G': return 'C';
    }
  }
  string rc(const string& s){
    int n=sz(s);
    vector<char> r(n);
    rep(i,n) r[n-1-i]=ct(s[i]);
    return string(all(r));
  }
 public:
  int getMaxSize(vector<string> dna) {
    int n=sz(dna);
    vector<string>adn(n);
    rep(i,n)adn[i]=rc(dna[i]);
    UF uf(n); // UnionFind
    rep(i,n)rep(j,n){
      if(i<j){
        if(adn[i]==dna[j]) uf.uSet(i,j);
      }
    }
    set<int> s;
    rep(i,n){
      s.insert(uf.root(i));
    }
    return s.size();
  }
};

Medium(500): Palindromize3

  • 残りあと10分ぐらいでログインできたので250をsubmitして500を開く
  • 文字列の長さが30とか
  • 最初と最後、2番目と最後から2番目、・・・半分に畳んで最大15組
  • どちらに合わせるか、で2^15通り
  • って全部試せるじゃん
  • 試すコード書く
  • できた(けど終了数分後でした)
...
#define sz(a)  int((a).size())
#define pb  push_back
#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++)
#define found(s,e)  ((s).find(e)!=(s).end())

#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)

class Palindromize3 {
 public:
  string getPalindrome(string s) {
    int l=sz(s);
    vector<pair<char,char> > cs;
    vector<int> pos;
    rep(i,l/2){
      char a=s[i],b=s[l-1-i];
      if (a!=b){
        if(a>b)swap(a,b);
        cs.pb(cons(a,b)); pos.pb(i);
      }
    }
    int o=sz(pos), z=1<<o;
    set<pair<int,string> > ss;
    rep(m,z){
      set<char> ds;
      for(int y=1,i=0;y<=z,i<o;y<<=1,i++){
        int pi=pos[i]; char u;
        if (m&y) {
          u = cs[i].first;
        } else {
          u = cs[i].second;
        }
        s[l-1-pi] = s[pi] = u;
        ds.insert(u);
      }
      ss.insert(cons(sz(ds),s));
    }
    return ss.begin()->second;
  }
};

Hard(1000): -

  • 問題みてない

Challenge Phase:

  • そもそもみんなほとんどsubmitできてないし

System Test

  • (o - -)
  • 当然ノーゲーム
  • Practice roomに500出したら通ったので満足しつつも(これが本番だったら多分予選通れたのにーーむぅー)
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100502