Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-04

SRM429 div2 (過去問)

18:51

Hard - IngredientProportions

カクテルのレシピが与えられる. まぜあわせるカクテルの種類ごとの割合が与えられる. 最終的に全体で何対何でまぜあわせればよいか求める.

アルゴリズムはストレートで, 実装をどうするか悩むたぐいの問題でした. まず, アルゴリズムは以下のようなシンプルなものです.

  1. スケールを無視して, すべてのカクテルの割合を求める
    • 例えばテストケース0だと{6, 4}, テストケース3だと{360, 120, 378, 504}
    • カクテルの割合のつながりを木で表現して, それを順にたどっていけばok
  2. 上記の数列の全要素に対する最大公約数を求め, それで割る

実装ですが, まず木は二次元配列で表現することにしました. 要素i, jに, iとjをまぜあわせるときのiの割合を格納します. これで木のつながりと混ぜる割合の両方を保存できます.

この木のすべてのノードを探索します. ここで探索の始点に注意が必要です. 僕は今回BFSで探索を実装したのですが, 木のルートか葉から出発しないとすべてのノードを探索してくれません. 木を表現する配列の行に有効な(0でない)値がひとつしかない場合, そのノードは葉となります. このようにして葉をみつけ, 探索の始点としています.

だらだらと書いていたので, コードが長くなってしまいました. もっと綺麗に書きたいです.

class IngredientProportions {
public:
  int gcd(const int _a, const int _b) {
    int a = max(_a, _b);
    int b = min(_a, _b);

    while (b) {
      int tmp = a % b;
      a = b;
      b = tmp;
    }

    return a;
  }

  vector <int> getMasses(vector <string> proportions) {
    vector <int> ret(proportions.size()+1, 0);
    int graph[proportions.size()+1][proportions.size()+1];
    memset(graph, 0, sizeof(graph));

    // 木の作成
    for (int i=0; i<proportions.size(); i++) {
      int num1 = proportions[i][1] - '0';
      int num2 = proportions[i][8] - '0';
      int ratio1 = proportions[i][13] - '0';
      int ratio2 = proportions[i][15] - '0';
      graph[num1][num2] = ratio1;
      graph[num2][num1] = ratio2;
    }

    //     for (int i=0; i<=proportions.size(); i++) {
    //       for (int j=0; j<=proportions.size(); j++)
    //         cout << graph[i][j] << " ";
    //       cout << endl;
    //     }

    queue <pair <int, int> > q;

    // 始点の探索
    for (int i=0; i<=proportions.size(); i++) {
      int counter = 0;
      int index = 0;
      for (int j=0; j<=proportions.size(); j++)
        if (graph[i][j] != 0) {
          counter++;
          index = j;
        }
      if (counter == 1) {
        q.push(make_pair(i, index));
        break;
      }
    }

    // bfs
    while (!q.empty()) {
      pair <int, int> cur = q.front();
      q.pop();

      int ratio1 = graph[cur.first][cur.second];
      int ratio2 = graph[cur.second][cur.first];
      graph[cur.second][cur.first] = 0;

      for (int i=0; i<=proportions.size(); i++)
        if (graph[cur.second][i] != 0)
          q.push(make_pair(cur.second, i));

      if (ret[cur.first] == 0 && ret[cur.second] == 0) {
        ret[cur.first] = ratio1;
        ret[cur.second] = ratio2;
      } else {
        int mul_for_cur = 0;
        int mul_for_exist = 0;
        int index = 0;
        if (ret[cur.first] != 0) {
          mul_for_cur = ret[cur.first] * ratio2;
          mul_for_exist = ratio1;
          index = cur.second;
        } else {
          mul_for_cur = ret[cur.second] * ratio1;
          mul_for_exist = ratio2;
          index = cur.first;
        }

        for (int i=0; i<ret.size(); i++)
          ret[i] *= mul_for_exist;

        ret[index] = mul_for_cur;
      }
    }

    // 最大公約数を求めて割る
    int divisor = ret[0];
    for (int i=1; i<ret.size(); i++)
      divisor = gcd(divisor, ret[i]);

    for (int i=0; i<ret.size(); i++)
      ret[i] /= divisor;

    return ret;
  }
};