Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-10-29SRM423

SRM423

SRM423 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM423 - naoya_t@topcoder SRM423 - naoya_t@topcoder のブックマークコメント

10.28+.2008

参加8回目。

DIVlevel問題名競技中後でSystem Test備考
1 250 TheTower 撃沈 o passed 10/31 https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081031/p1 61.35%
1 500 TheEasyChase 途中
1 1000 TheBeautifulBoard -

250点問題: TheTower

→チャレンジタイムで撃沈

500点問題: TheEasyChase

時間切れ。

0点。

室内の500点は全機撃墜されていた。250点が7,8人残る程度。

レーティング少し落ちて 1460 → 1417。寝倒した西尾さん(1465)との差が開く。

http://gyazo.com/4b812a646a04323d17cdad1243e2c16d.png

コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081029

2008-10-23

SRM420 Div1 Hard: ChangeOMatic

過去問, 練習 | 18:13 | SRM420 Div1 Hard: ChangeOMatic - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM420 Div1 Hard: ChangeOMatic - naoya_t@topcoder SRM420 Div1 Hard: ChangeOMatic - naoya_t@topcoder のブックマークコメント

1000点問題の練習。（問題文はこちら。要TopCoderアカウント）

  • すぐにコーディングを始める方式をやめて、先にノートに考えをまとめる方式に移行中。
  • 問題文のTestCase 4で、想定される37ではなく34が出てしまう
    • 120 → 100 + 12 + 8 の後、100の分割が悪かった。
    • 12*7 + 8*2 = 100 が出せてない。
  • priority queueを使って最小枚数かつ辞書順最大の組合せを得られるルーチンは書けた。しかしこれは大きな数の入力に非常に弱い（数十万程度でも遅い）ので、問題文のTestCase程度にしか対応できない。
  • 少ないコイン枚数の（かつ辞書順で一番大きい）組合せを、大きな数（10^15まで）の入力に対し「高速に」得るロジックを（数学的にきちんと）考え直さないといけない。← いまここ
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081023

2008-10-22

SRM421 Div1 Easy: EquilibriumPoints

過去問, 練習 | 18:13 | SRM421 Div1 Easy: EquilibriumPoints - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM421 Div1 Easy: EquilibriumPoints - naoya_t@topcoder SRM421 Div1 Easy: EquilibriumPoints - naoya_t@topcoder のブックマークコメント

前々回のSRMの250点問題。途中で訳がわからなくなって500点問題１本に絞った回。

やはりbinary searchですんなり書けた。精度が１桁足りなくてシステムテストで落ちた。直した。

doubleでabsしたい・・・それ<cmath>でできるよ

３分割でやってる人がいるとかどこかで読んだので比較してみた。１度に1/3に狭められるけれど、その１度の計算量が5/3ぐらいなのであまりメリットがないように思える。（1/2なら5回で1/32まで絞り込めるが、1/3は3回で1/27までしか行かない）

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点問題のコーディングは初挑戦。

  • Worker１人がそれぞれ 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
    • とりあえずナイーブに辿れるルートをカウント（一度通った道は通れない）
    • W = W を入れることで、同じWを使うルートがいくつも出来てしまうのを防ぐことができる。
    • residual networkを作って、カウントを増やしていく（問題文のテストケースでは、residual networkが必要な問題はない）

submitしてみたが、System Testの６番（マップ大きめ）で落ちる。

  • マップ内の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

コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081022

2008-10-20

SRM422 Div1 Medium: CavePassage

過去問, 練習 | 18:13 | SRM422 Div1 Medium: CavePassage - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM422 Div1 Medium: CavePassage - naoya_t@topcoder SRM422 Div1 Medium: CavePassage - naoya_t@topcoder のブックマークコメント

（15分オーバーで書いた6.8秒で解けるコードでは複数人が戻ってくるケースが想定外。・・・これはダイクストラで解くべき問題のようです。）

BFS x priority_queueとかいろいろ試行錯誤した挙げ句ダイクストラで書き直してみたけど、システムテストの中に通らないケースがいくつか(#15,#21)ある。問題を読み違えているのかな。

とりあえず晒してみる: 

#include <vector>
#include <string>
#include <set>
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())

#define HOME 0
#define AWAY 1

class CavePassage {
public:
  int minimalTime(vector<int> travelersWeights,
                  vector<int> travelersTimes,
                  vector<string> trustTable,
                  int bridgeStrength) {

    int nn = travelersWeights.size();
    int patterns = 1 << nn;
    int all_mask = patterns - 1;
    int start = 0, goal = all_mask;

    set<int> possibles;
    vector<int> weight(patterns, INT_MAX);
    vector<int> minute(patterns, INT_MAX);

    for (int m=1; m<=all_mask; m++) {
      int weight_ = 0, minute_ = 0;
      for (int i=0,mi=1; i<nn; i++,mi<<=1) {
        if (mi & m) {
          weight_ += travelersWeights[i];
          minute_ = max(minute_, travelersTimes[i]);
        }
        if (weight_ > bridgeStrength) goto impossible;

        if (__builtin_popcount(m) >= 2) {
          int trust_count = 0;
          const char *cs = trustTable[i].c_str();
          for (int j=0,mj=1; j<nn; j++,mj<<=1) {
            if (j != i && (mj & m)) {
              if (cs[j] == 'Y') trust_count++;
            }
          }
          if (trust_count == 0) goto impossible;
        }
      }
      weight[m] = weight_;
      minute[m] = minute_;
      possibles.insert(m);
    impossible:
      continue;
    }
    if (possibles.size() == 0) return -1;

    vector<vector<int> > distance_to_fix(2);
    vector<vector<int> > distance_fixed(2);
    for (int i=HOME; i<=AWAY; i++) {
      distance_to_fix[i].resize(patterns);
      distance_fixed[i].resize(patterns);
      for (int j=0; j<=all_mask; j++)
        distance_to_fix[i][j] = distance_fixed[i][j] = INT_MAX;;
    }

    distance_fixed[HOME][start] = 0;

    tr(possibles,it) {
      distance_to_fix[AWAY][*it] = minute[*it];
    }

    while (1) { // while (distance_fixed[AWAY][goal] == -1) {
      int distance_min = INT_MAX;
      for (int j=1; j<=all_mask; j++)
        for (int i=HOME; i<=AWAY; i++)
          if (distance_to_fix[i][j] < distance_min) distance_min = distance_to_fix[i][j];
      if (distance_min == INT_MAX) break;

      for (int j=1; j<=all_mask; j++) {
        for (int i=HOME; i<=AWAY; i++) {
          if (distance_to_fix[i][j] == distance_min) {
            distance_fixed[i][j] = distance_min;
            distance_to_fix[i][j] = INT_MAX;
            if (i == AWAY && j == goal) return distance_min;

            tr(possibles,it) {
              int m = *it;
              if ((j & m) == (i == HOME ? 0 : m)) {
                int d = distance_min + minute[m];
                int at = (i == HOME)? j + m : j - m;
                if (i == AWAY && (at == start || at == goal)) continue;
                if (distance_fixed[1-i][at] == INT_MAX)
                  if (d < distance_to_fix[1-i][at]) distance_to_fix[1-i][at] = d;
              }
            }
          }
        }
      }
    }
    return -1;
  }
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081020

2008-10-19SRM422

SRM422

SRM422 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM422 - naoya_t@topcoder SRM422 - naoya_t@topcoder のブックマークコメント

10.18+.2008

TopCoder SRM (Single Round Match) 参加７回目。DIV1では４回目。

Boost禁止令が出た。けどそもそも使ってなかったのでスルー。

DIVlevel問題名競技中後でSystem Test備考
1 250 PrimeSoccer ◎ passed 99.51%
1 500 CavePassage 途中 △ x15,21 10/20 https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081020/p1
1 1000 WorkersOnPlane - o passed 10/22 https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081022/p1

250点問題: PrimeSoccer

最近Project Eulerにはまっているせいか、これは比較的簡単に思えた。186.71点

500点問題: CavePassage

15分ぐらい足りなかった。（解けたけどchokudaiさんの撃墜ケースを通したらローカルで6.8秒かかった。これはサーバ上で通るか微妙なライン。）

250点×1で186.71点。

  • チャレンジタイム：耐えた
  • システムテスト：OK

DIV1全体で383/723位。

レーティングは落ちるかと思ったけど 1441 → 1460 に微上昇。もう少しで西尾さん(1465)。もう少しで黄色。

http://gyazo.com/eea98d4576b0a6287a80522feac933bb.png

今日覚えた単語 (thanks to chokudai)

  • TLE: Time Limit Exceeded
  • WA: Wrong Answer

TopCoder部のSkypeチャットが良い刺激になっている。GJ>suztomo

追記

  • 250点問題みんなDP使ってますね。最近Project Euler脳なせいか、これは計算式で一発、みたいな。
  • 500点問題、6.8秒で解けるコードでは複数人が戻ってくるケースが想定外。これはダイクストラで解くべき問題のようです。（続く）
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081019
naoya_t
→TopCoder Member Profile
→日本人参加者ランキング
→PKU日記はこちら
カレンダー
<< 2020/01 >>
日 月 火 水 木 金 土
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
注目エントリー
自作ライブラリ
最近のコメント
最近のトラックバック
最新日記一覧