Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-10-22

SRM422 Div1 Hard: WorkersOnPlane

| 18:13 | SRM422 Div1 Hard: WorkersOnPlane - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM422 Div1 Hard: WorkersOnPlane - naoya_t@topcoder SRM422 Div1 Hard: WorkersOnPlane - naoya_t@topcoder のブックマークコメント

練習のために前回(SRM 422)のDIV1 1000点問題「WorkersOnPlane」を開いてみた。1000点問題のコーディングは初挑戦。

  • Worker1人がそれぞれ Gold x 1, Silver x 1 を担当。
  • W(Workplace)から距離K以内のG(Gold),S(Silver)のみ担当可能。マップには途中障害物あり。

解けるかも・・・

  1. マップを走査し、W,G,Sを探してそれぞれにidを振る
  2. 各Wから到達可能なG,Sをすべて抽出
    • WからK以内で到達可能な領域をFlood Fill的にBFS(+priority queue)探索
    • どこからも到達不能なG,Sはネットワークに入れない
  3. W-G-S の組をできるだけ多く作る

やっとMaximum Flowを使える問題が来たよ

    • start < G x W = W x S > end
      • G,W,Sはそれぞれ複数ノード。
      • x は複数の辺がクロスしているイメージ。
      • = は1対1で平行に繋がっている
      • <, > は1対多で繋がっている
    • 各辺のキャパシティは1
    • とりあえずナイーブに辿れるルートをカウント(一度通った道は通れない)
    • W = W を入れることで、同じWを使うルートがいくつも出来てしまうのを防ぐことができる。
    • residual networkを作って、カウントを増やしていく(問題文のテストケースでは、residual networkが必要な問題はない)

submitしてみたが、System Testの6番(マップ大きめ)で落ちる。

  • マップ内のSの個数がW,Gと違った
  • 一度通った道は通れない、ようにしたつもりだったがチェックしていない箇所があったorz

で無事「120」が出るようになった。

これを時間内に解ければ点が貰えるんですね。

時間内に・・・><

書いたコードを晒してみる:

#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;

#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

class WorkersOnPlane {
public:
  int howMany(vector<string> field, int K) {
    int rows = field.size();
    int cols = field[0].size();
    
    vector<pair<int,int> > W;
    
    map<pair<int,int>, int> G, S;
    int gcount = 0, scount = 0;
    
    for (int y=0; y<rows; y++) {
      for (int x=0; x<cols; x++) {
        int c = field[y][x];
        switch (c) {
        case 'W': W.push_back( make_pair(y,x) ); break;
        case 'G': G[ make_pair(y,x) ] = gcount++; break;
        case 'S': S[ make_pair(y,x) ] = scount++; break;
        default: break;
        }
      }
    }
    int wcount = W.size();
        
    int nodes = 1 + gcount + wcount * 2 + scount + 1;
    const int START = 0,
      GSTART = 1,
      WgSTART = GSTART + gcount,
      WsSTART = WgSTART + wcount,
      SSTART = WsSTART + wcount,
      END = nodes - 1; // SSTART + scount
    vector<map<int,pair<int,int> > > arc(nodes);
    
    for (int g=0; g<gcount; g++) arc[START][GSTART+g] = make_pair(0,1);
    for (int w=0; w<wcount; w++) arc[WgSTART+w][WsSTART+w] = make_pair(0,1);
    for (int s=0; s<scount; s++) arc[SSTART+s][END] = make_pair(0,1);
    
    for (int w=0; w<wcount; w++) {
      int y = W[w].first, x = W[w].second;
      
      vector<vector<int> > d(rows); // distance
      for (int y=0; y<rows; y++) {
        d[y].resize(cols);
        for (int x=0; x<cols; x++) {
          d[y][x] = INT_MAX;
        }
      }
      priority_queue<pair<int,pair<int,int> > > pq;
      
      pq.push(make_pair(0,make_pair(y,x)));
      
      do {
        int y = pq.top().second.first;
        int x = pq.top().second.second;
        int d_ = -pq.top().first;
        pq.pop();

        if (d_ >= d[y][x]) continue;
        
        switch (field[y][x]) {
        case 'W':
          if (d_ != 0) break;
          // fall through
        case '.':
          d[y][x] = d_; //min(d_, d[y][x]);
          if (d_ < K) {
            if (x >= 1)
              pq.push(make_pair(-d_-1,make_pair(y,x-1)));
            if (x+1 < cols)
              pq.push(make_pair(-d_-1,make_pair(y,x+1)));
            if (y >= 1)
              pq.push(make_pair(-d_-1,make_pair(y-1,x)));
            if (y+1 < rows)
              pq.push(make_pair(-d_-1,make_pair(y+1,x)));
          }
          break;
        case 'G':
          {
            d[y][x] = d_;
            int g = G[ make_pair(y,x) ];
            arc[GSTART+g][WgSTART+w] = make_pair(0,1);
          }
          break;
        case 'S':
          {
            d[y][x] = d_;
            int s = S[ make_pair(y,x) ];
            arc[WsSTART+w][SSTART+s] = make_pair(0,1);
          }
          break;
        case 'X':
          break;
        }

      } while (!pq.empty());
      
    }

    // remove unreachable Gs/Ss
    for (int g=0; g<gcount; g++) {
      if (arc[GSTART+g].size() == 0) {
        arc[START].erase(GSTART+g);
      }
    }
    vector<bool> ss(scount,false);
    for (int w=0; w<wcount; w++) {
      tr(arc[WsSTART+w],st) { ss[st->first - SSTART] = true; }
    }
    for (int s=0; s<scount; s++) {
      if (!ss[s]) {
        arc[SSTART+s].erase(END);
      }
    }

    // initial
    vector<vector<int> > ways;
    for (int g_=0; g_<gcount; g_++) {
      int g = GSTART+g_;
      
      bool viable = false;
      tr(arc[g],at) {
        if (at->second.first == 1) continue;
        int w = at->first; // key

        if (arc[w][w+wcount].first == 1) continue;
        tr(arc[w+wcount],bt) {
          // bt = arc[ws][s]
          if (bt->second.first == 1) continue;
          int s = bt->first; // key
          if (arc[s][END].first == 1) continue;
          int way_[6] = { START, g, w, w+wcount, s, END };
          vector<int> way(way_, way_+6);
          ways.push_back(way);
          arc[START][g].first = 1; // START - G
          arc[g][w].first = 1; // G - Wg
          arc[w][w+wcount].first = 1; // Wg - Ws
          arc[w+wcount][s].first = 1; // Ws - S
          arc[s][END].first = 1; // S - END
          viable = true;
          break;
        }
        if (viable) break;
      }
    }

    // residual networks
    vector<map<int,int> > resid(nodes);
    for (int j=0; j<nodes; j++) {
      tr(arc[j],at) {
        int k = at->first;
        resid[j][k] = arc[j][k].second - arc[j][k].first;
        resid[k][j] = arc[j][k].first;
      }
    }
    
    if (ways.size() == arc[START].size()) return ways.size();

    // find another way
    for (int i=0; ;i++) {
      bool another_way = false;

      vector<int> prev(nodes,INT_MAX);
      queue<pair<int,int> > q;

      q.push(make_pair(START,-1));

      while (!q.empty()) {
        pair<int,int> p = q.front();
        int node = p.first, prev_node = p.second;
        q.pop();

        prev[node] = prev_node;
        if (node == END) {
          another_way = true;
          break;
        }
        
        tr(resid[node],rt) {
          if (rt->second == 0) continue;
          if (prev[rt->first] < INT_MAX) continue;
          q.push(make_pair(rt->first, node));
        }
      }
      // no more ways
      if (!another_way) return ways.size() + i;

      for (int node=END; node!=START; node=prev[node]) {
        int prev_node = prev[node];
        resid[prev_node][node]--;
        resid[node][prev_node]++;
      }
    }

    return 0;
  }
};
  • Ford-Fulkerson法
  • この問題では ways[] に見つかった経路を保持する意味合いは特にない。ちゃんと見つかっているかどうかデバッグ時に知るのに役に立つだけ。

追記

nitoyonさんの裏ログに解説がw