naoya_t@topcoder

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

10:02 |

Easy(250): DNAMatching

• 各DNAについて、左右反転してA⇔T,G⇔Cを交換したものを用意
• お互いに比較し、マッチしてる組み合わせを辺としたグラフを考えたら隣接行列ができる
• はて
• 最大ノーペア数どうやって出したらいいんだ
• ノートに書いて考える
• とりあえずグラフでくっついてるものを島にして、各島から１ノードずつ代表を出せば最大ノーペアが出来るんじゃないか
• union-findで
  • http://www.prefield.com/algorithm/container/union_find.html
• あれどうやって島の数数えるんだっけ
• ごにょごにょ
• できた！
• あれ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出したら通ったので満足しつつも（これが本番だったら多分予選通れたのにーーむぅー）