cafelier@SRM

SRM435 Div1

SRM | 13:48 |

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秒。大丈夫だ

• 「子から親への（元のグラフでの）パスがあってはいけない」という条件は、要するに絶対にツリーにするときに使ってはいけない辺があるというだけの条件か
• 「兄弟間に（元のグラフでの）ループがあってはいけない」は、ツリーにするときに両方使ってはいけない辺ペアという条件になる
• あとツリーを作るというのは、親が２つあってはいけないということなので、これも両方使ってはいけない辺ペアという条件になる
• この辺の制約は前処理して静的に求めておけるな…

• 『最大2500個の使っていい辺のうち、いくつかのペアには同時に使ってはいけないという制約がかかっている。連結成分の個数をできるだけ少なくするように辺を選べ』
• という問題になった。
• 「連結成分の個数」って評価関数はどう評価すればいいのだ。わからん。

• 時間切れ

撃墜タイム

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

感想

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

SRM435 1000

あとで | 21:44 |

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

// 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);
  }
};

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

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

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

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