Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2009-02-13

SRM435 Div1

| 13:48 | はてなブックマーク -  SRM435 Div1 - cafelier@SRM

SRM435 の成績・ソース (要ログイン) : AC/AC/- : だんだんチャレンジ恐怖症になってきた


500開く

  • 『2500文字以下のDNA(A,T,G,Cの文字列)と、"3文字->アミノ酸"のマッピング(50マッピング以下)が与えられるので、適当に文字削除して3文字毎に区切って左から右にアミノ酸化して作れるアミノ酸列は何パターンあるか。mod 1000000007で。』
  • mod 1000000007 と言ってるので探索はない。
  • まあ2500^2*50くらいのDPでしょ
  • アミノ酸の個数でループ回すとどうだ
    • 1個目を作る作り方全パターン(i文字目まで使うやり方はn通り、みたいなテーブル)を求める
    • 2個目を作る作り方全パターン(i文字目まで使うやり方はn通り、みたいなテーブル)を求める
    • ...
  • 「i文字目まで…」で持つとだめだなー。重複カウントしてしまう。10文字目までで[a,b,c]を作るパターンと20文字目までで[a,b,c]を作るパターンとかそういうのを。
  • かといって[a,b,c]とかのパターンを全部覚えたら計算量が指数だ。

  • えーと
  • いや、[a,b,c]を作るときは常に最左で作るパターンだけ考えればいいんじゃね?
    • さっきのだと20文字目まで使う方は捨てればいい
    • 他で作れるなら最左で作れるパターンからでも作れるので

  • ちょっと頭を整理しよう
  • dna[0...i] を使って作れるアミノ酸列のパターン数を dp[i] とする。
    • このとき、dna[0...i] でも作れるけどもっと短い dna[0..j], j<i でも作れるようなパターンはカウントしない
  • dp[k] = Σ{dp[i]*u | i=0~k, u=dna[i...k]でちょうどぴったり1個アミノ酸作る作り方}
  • だ。
  • ちょうどぴったり作れるかどうかは、iからkまでループ回して、まあ適当になんとかなる

  • というわけで、個数というよりはDNA上のインデックスで回すDP的なもの
    • dp[k]の計算の時にうしろを参照するよりは、dp[i]の計算の時に表の先の方に足し込んでいってΣを計算する感じになった
  • できた
  • サンプル通った。まああってるでしょう多分。えいや。

250開く

  • 『親の番号の配列、という形式で2分木が与えられる。あと、死んでるノードの番号が与えられる。死んでるノードの子孫でない葉ノードの個数は?』
  • 書くだけ問題
  • …と思ったけど部屋に245点越えてる人がいない。なにか勘違いしてるかな…
  • 全てのノードについて親方向に上っていって
    • 何はともあれご先祖様全部にフラグたてる
    • 死んでるノードが見つかったら自分にフラグたてる
  • フラグ立ってないノードの数をカウント。おしまい。
  • できた。サンプル通った。
  • って自分も240点とかだ。こんなもんかー。
  • サブミット。

1000開く

  • 問題長いなあ。整理すると…
    • 『50点以下の有向グラフが与えられる。辺を適当に削って複数のツリーにせよ。ツリーの個数を最小にするように。ただし
      • 子から親への(元のグラフでの)パスがあってはいけない
      • 兄弟間に(元のグラフでの)ループがあってはいけない

  • さっぱりわからぬ
  • とりあえず強連結成分分解したら強連結成分の中身だけ考えればいいようにならないだろうか
    • ならない
    • うーん

  • 悩んでいるうちに500がTLEにならないか不安になってきた
    • 適当に最大ケースを作って試してみる
    • 手元で1秒。大丈夫だ

  • 「子から親への(元のグラフでの)パスがあってはいけない」という条件は、要するに絶対にツリーにするときに使ってはいけない辺があるというだけの条件か
  • 「兄弟間に(元のグラフでの)ループがあってはいけない」は、ツリーにするときに両方使ってはいけない辺ペアという条件になる
  • あとツリーを作るというのは、親が2つあってはいけないということなので、これも両方使ってはいけない辺ペアという条件になる
  • この辺の制約は前処理して静的に求めておけるな…
  • 『最大2500個の使っていい辺のうち、いくつかのペアには同時に使ってはいけないという制約がかかっている。連結成分の個数をできるだけ少なくするように辺を選べ』
  • という問題になった。
  • 「連結成分の個数」って評価関数はどう評価すればいいのだ。わからん。
  • 時間切れ

撃墜タイム

  • 250を非常に怪しげな解き方をしてる人がいたので、10分考えて「これだ!」という例を突っ込んだものの、失敗。
    • もうだめぽ
  • しかもその人のコードSystem Testで落ちてるよ!僕の目は間違ってなかった!

感想

  • 500はもう少しスピーディに解けてもよかった
  • 1000全然解けないなー。まずいなー。

SRM435 1000

| 21:44 | はてなブックマーク -  SRM435 1000 - cafelier@SRM

惜しいところまでは行ってたようだ。

// 2部グラフの最大マッチ ----------------------------
typedef int           vert;
typedef vert          edge;
typedef vector<edge>  edges;
typedef vector<edges> graph;

bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
{
  for(int i=0; i<G[v].size(); ++i) {
    vert u = G[v][i];
    if( visited[u] ) continue;
    visited[u] = true;

    if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
      { matchTo[v]=u, matchTo[u]=v; return true; }
  }
  return false;
}

template<int NV>
int biMatch( graph& G, int L )
{
  vector<vert> matchTo(G.size(), -1);
  int ans = 0;
  for(vert v=0; v<L; ++v) {
    bool visited[NV] = {};
    if( augment(G, v, matchTo, visited) )
      ++ans;
  }
  return ans;
}

// 本体 -------------------------------------------
class CompanyRestructuring {
public:
  int fewestDivisions(vector <string> hasManaged) 
  {
    int N = hasManaged.size();

    bool hm[50][50], hmStar[50][50];
    for(int i=0; i<N; ++i)
      for(int j=0; j<N; ++j)
        hm[i][j] = hmStar[i][j] = hasManaged[i][j]=='Y';

    for(int k=0; k<N; ++k)
      for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
          hmStar[i][j] |= hmStar[i][k] & hmStar[k][j];

    graph g(N);
    int nextID = N;
    for(int p=0; p<N; ++p)
    {
      vector<int> cs;
      vector<int> pi;

      for(int c=0; c<N; ++c)
        if( hm[p][c] && !hmStar[c][p] )
        {
          int pid = -1;
          
          for(int j=0; j<cs.size(); ++j)
            if( hmStar[c][cs[j]] && hmStar[cs[j]][c] )
              {pid = pi[j]; break;}

          if(pid<0) pid = nextID++;
          cs.push_back(c);
          pi.push_back(pid);
          g[c].push_back(pid);
        }
    }
    g.resize(nextID);

    return N - biMatch<50*50*2>(g, N);
  }
};

辺を1個つかうごとに連結成分の個数は1個減るので、「連結成分の個数」って評価関数は単純に「使う辺が多ければ多いほどよい」に他ならない。

まずは「兄弟間に(元のグラフでの)ループがあってはいけない」という条件を無視して考えると、

  • 左側にN点、右側にN*N点のグラフを作って最大マッチ
    • 左の x 番目と右の N*y+x 番目を結ぶことと、x の親を y とすることが対応する
    • 親は1つ(ルートなら0個)という条件は、マッチングなので左のxから出る辺を2本同時に選んだりしないことで表現
    • グラフを作るときに、「親からは子へは(元のグラフでの)パスがある」「子から親への(元のグラフでの)パスがあってはいけない」という条件を満たす辺だけをあらかじめ入れておく。これを満たしていればツリーがDAGしか作らないのでその辺の制約もOK

という作り方。「兄弟間に(元のグラフでの)ループがあってはいけない」という条件は、この関係が同値関係なことを考えると、親を表す右のノードを N*y+x と全部別々にするんじゃなくて、兄弟になれないxどうしは同じ親ノードを指すようにグラフを作る。これでマッチングという条件から親を共有しないという条件が加味される。

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20090213
 | 

presented by cafelier/k.inaba under CC0