Hatena::Grouptopcoder

blu_rayの日記

2011-09-21

SRM 519 Div2

| 19:02

寝過ごしたのでPractice ...

250. WhichDay

やさしい。

600. ThreeTeleports

色々考えることが出来そうですが、面倒くさいので全探索。

ワープの組は3つなので全部を通っていく場合は3!、さらにEndPointへの行き方は(x1,y1) -> (x2,y2), (x2,y2) -> (x1,y1) の2通りが存在するので、ワープへの入り方で2^3の状態を生成すれば良さそう。

書いたら計算量も3! * 2^3 * 3.

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

struct EndPts {
  int x1, y1, x2, y2;
};
EndPts endPts[3];

class ThreeTeleports {
public:
  int calc(int ax, int ay, int bx, int by) {
    return abs(ax-bx) + abs(ay-by);
  }
  void setEndPts(const vector<string>& teleports) {
    int i, j;
    rep (i, 3) {
      int cur = 0;
      vector<int> v;
      rep (j, teleports[i].size()) if (teleports[i][j] == ' ') v.push_back(j);
      v.push_back(teleports[i].size());
      int ti[4];
      rep (j, 4) {
        ti[j] = atoi(teleports[i].substr(cur, v[j] - cur).c_str());
        cur = v[j]+1;
      }
      endPts[i] = (EndPts){ti[0], ti[1], ti[2], ti[3]};
    }
  }
  int shortestDistance(int xMe, int yMe, int xHome, int yHome, vector<string> teleports) {
    int i;
    long long ans = calc(xMe, yMe, xHome, yHome);
    setEndPts(teleports);
    int a[3] = {0,1,2};
    do {
      for (int S = 0; S<(1<<3); S++) {
        long long temp = 0;
        int x = xMe, y = yMe;
        rep (i, 3) {
          int t = a[i];
          if ((1<<i) & S) {
            temp += calc(x, y, endPts[t].x1, endPts[t].y1) + 10;
            x = endPts[t].x2, y = endPts[t].y2;
          } else {
            temp += calc(x, y, endPts[t].x2, endPts[t].y2) + 10;
            x = endPts[t].x1, y = endPts[t].y1;
          }
          ans = min(ans, temp + calc(x, y, xHome, yHome));
        }
      }
    } while (next_permutation(a, a+3));
    return ans;
  }
};

teleportsのデータの読み取りはsscanfとかistringstream使えば良かった。。

900. BinaryCards

他の人コード読んで理解。aとbのbitを調べるときに

// 問題無し
int i;
for (i .. ) if ((a >> i & 1)^(b >> i & 1)) {
  ..
}
// 問題あり
for (i .. ) if (((1 << i) & a)^((1 << i) & b)) {
  ..
}

1<<iってintになるのか</ppp>