Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-09

SRM447 div2 (過去問)

22:54

Hard - ImportsList

いくつかのスクリプトがあり, それぞれ別のスクリプトインポートしなければいけない. 各スクリプトについて, インポートする数を最小化する.

この問題には感動しました. いまいち良い解が見つからなかったので, レッドコーダーの方々のコードを見ていたのですが, だいたいの人はfloyd-warshallアルゴリズムをうまく応用して, 非常にスマートに解いていました. アイデアは, 例えばスクリプトiからスクリプトjをインポートする必要がある場合を考えると, もし別のスクリプトk(iはkもインポートする必要があるとする)がjをインポートしていた場合, iからjを直接インポートするよりも, kを経由してインポートした方がインポート数を節約できます. この操作を, 三重ループによってすべての組み合わせに適用します. floyd-warshallはグラフ上のノードのすべての組み合わせについて最短経路を求めるアルゴリズムです. それをこんな風に応用するアイデアは自分には思いつきませんでした.

class ImportsList {
public:
  vector <int> importsCount(vector <string> requires) {
    vector <int> ret(requires.size(), 0);
    vector <string> result = requires;
    int n = requires.size();

    for (int i=0; i<n; i++)
      for (int j=0; j<n; j++)
        for (int k=0; k<n; k++)
          if (requires[i][k] == 'Y' && requires[k][j] == 'Y')
            result[i][j] = 'N';

    for (int i=0; i<n; i++)
      for (int j=0; j<n; j++)
        if (result[i][j] == 'Y')
          ret[i]++;

    return ret;
  }
};