naoya_t@topcoder

SRM410 Div1 Easy: AddElectricalWires

過去問, 練習 | 18:07 |

これ250点問題だけどちょっと難しい。サンプルケースが通った程度では安心できない。通過率も53.71%でMediumより低い。

• gridに繋がっているノードをまとめる
  • いちばん多く繋がっているgridはどれか
• gridに繋がっていないノードは全て、いちばん多く繋がっているgridに繋げる
• 各gridについて、同じgridに繋がるノードは全て繋ぐ
• 最初からあるコネクションの数を引く

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

class AddElectricalWires {
  vector<vector<bool> > w;
  vector<int> gC;
  int nw, ngc;

  void turn(int orig,int dest) {
    rep(i,nw) if (gC[i]==orig) gC[i]=dest;
  }

public:
  int all_connections(int n) { return (n>=2) ? n*(n-1)/2 : 0; }
    
  int maxNewWires(vector<string> wires, vector<int> gridConnections) {
    nw = wires.size(); // 1-50
    ngc = gC.size(); // 1-50

    gC.resize(nw); rep(i,nw) gC[i]=-i-1;
    tr(gridConnections,it) gC[*it]=*it;

    int conn = 0;
    w.resize(nw); tr(w,it) it->resize(nw);
    rep(i,nw) rep(j,nw) {
      w[i][j] = (wires[i][j]=='1');
      if (i<j && w[i][j]) {
        conn++;
        turn(min(gC[i],gC[j]), max(gC[i],gC[j]));
      }
    }
    rep(i,nw) if (gC[i]<0) gC[i] = -1;

    vector<int> count(nw+1,0);
    rep(i,nw) count[1+gC[i]]++;

    int maxc = 0, maxc_at = -1;
    for (int i=1;i<=nw;i++)
      if (count[i] > maxc) {
        maxc = count[i]; maxc_at = i;
      }
    if (maxc_at < 0) {
      return all_connections(nw) - conn;
    } else {
      count[maxc_at] += count[0];
      int ans = 0;
      for (int i=1;i<=nw;i++) ans += all_connections(count[i]);
      return ans - conn;
    }
  }
};