Hatena::Grouptopcoder

どせいふんとうき。 RSSフィード

2013/03/26

SRM 574

| 06:32 | はてなブックマーク - SRM 574 - どせいふんとうき。

撃沈回. 250, 500 点問題を提出してどちらもシステムテストで落ちました.というわけで問題の点数は 0 点.しかし 500 点問題でこれはひっかかりそう!という部分がわかったので 3 つほど撃墜しました.というわけで総合スコアは 150 点.レーティングは 1134 -> 1024 とがっくり落ちました.

CityMap: Failed System Test

解き方はすぐに思いついたのですが,サンプルテストで理解できないエラーを連発しました.結局,そのまま提出して,案の定システムテストで蹴られました.コンテスト終了後にコードを眺めていたら原因がわかりました.アホなミスをしたなぁと反省しています.

class CityMap {
  public:
  string getLegend(vector <string> cityMap, vector <int> POIs) {
    vector<int> counts(27,0);
    string s("");
    int H = cityMap.size();
    int W = cityMap[0].size();
    for (int h=0; h<H; ++h) {
      for (int w=0; w<W; ++w) {
        if (cityMap[h][w]=='.') continue;
           // ↑の行を忘れていたせいで死んでいました……
        counts[cityMap[h][w]-'A']++;
      }
    }
    int N = POIs.size();
    vector<int>::iterator cit = counts.begin();
    for (int n=0; n<N; ++n) {
      cit = find(counts.begin(),counts.end(),POIs[n]);
      s += (cit-counts.begin())+'A';
    }
    return s;
  }
};

TheNumberGameDiv2: Failed System Test

システムテストで蹴られたのは {999999, 9} みたいな入力でした.数字の反転を一回もしなくていい場合を想定していませんでした.抜けてました.

チャレンジフェーズで他の人のコードを眺めながら,貪欲に探索していけばもっと簡単に書けそうだと気づきました.ということで練習ではその方針でクリアしました.

class TheNumberGameDiv2 {
  public:
  int reverse(int N) {
    int R(0);
    while(N>0) {
      R *= 10; R += N%10; N /= 10;
    }
    return R;
  }
  int cutint(int N) {
    return N/10;
  }
  int minimumMoves(int A, int B) {
    queue< pair<int, int> > Q;
    stringstream sA; sA << A;
    Q.push(make_pair(A,0));
    while (Q.size()) {
      int cur  = Q.front().first;
      int cost = Q.front().second;
      if (B==cur) return cost;
      Q.pop();
      int r = reverse(cur);
      int c = cutint(cur);
      if (r>0) Q.push(make_pair(r,cost+1));
      if (c>0) Q.push(make_pair(c,cost+1));
      if (cost > sA.str().size()+2 ) break;
    }
    return -1;
  }
};

PolygonTravarsal2: Opened

他の対角線と交差しているかどうかの判定で苦戦しました.結局完成せずに終了.あとは終了判定でも問題の条件をスルーしている部分がありました.いけませんね.

深さ優先で探索していって最後まで辿りつけたら 1 を返す→どんどん足し合わせる,というプランで問題なくクリアすることができました.

class PolygonTraversal2 {
  public:
  bool is_intersect(int from, int to, vector<int> points) {
    int f = 0;
    int t = to - from;
    int N = points.size();
    for (int i =0; i<N-1; ++i) {
      int x1 = points[i] - from;
      int x2 = points[i+1] - from;
      if (f < x1 && x1 < t && t < x2) return true;
      if (f < x2 && x2 < t && t < x1) return true;
      if (x1 < f && f < x2 && x2 < t) return true;
      if (x1 < t && t < x2 && x2 < f) return true;
      if (t < x1 && x1 < f && f < x2) return true;
      if (t < x2 && x2 < f && f < x1) return true;
      if (x2 < f && f < x1 && x1 < t) return true;
      if (x2 < t && t < x1 && x1 < f) return true;
    }
    return false;
  }
  int run(int N, vector<int> points) {
    int cnt(0);
    int len = points.size();
    int tail = points[len-1];

    if (len==N) {
      if (is_intersect(tail,points[0],points)) {
        return 1;
      } else {
        return 0;
      }
    }

    vector<int>::iterator pb = points.begin();
    vector<int>::iterator pe = points.end();
    for (int i = 1; i <= N; ++i) {
      if (find(pb,pe,i)!=pe) continue;
      if (!is_intersect(tail,i,points)) continue;
      vector<int> p = points; p.push_back(i);
      cnt += run(N,p);
    }
    return cnt;
  }
  int count(int N, vector <int> points) {
    return run(N,points);
  }
};

Challenge: 150.00

500 点問題を 3 つ撃墜しました.初撃墜成功(「・ω・)「

使用した入力は {43212345, 234} です.最初に「A が B を含む」「逆順 A が B を含む」の場合分けをしている人はだいたいこれで落ちてくれました.


次回は問題をクリアして点をとりたいです(´;ω;`)