Hatena::Grouptopcoder

blu_rayの日記

2011-11-30

SRM 525 Div2

| 06:40

ox-

無理。

250. RainyRoad / Passed : 168

まんまとBFSで出してしまう。遅い。

600. DropCoins / Failed

Challenge Phase始まって1分くらいで撃墜される。TLE

全部終わった後、泣きながらPracticeRoomのwriterさんのコードを見る。

わざわざO(n^4)の解き方とO(n^6)の解き方があって丁寧さに泣ける。

O(n^6)の方を写経して、自分で最悪ケースでチャレンジしたら死んだけど、6重ループでも出来てる人がいるので、なんか工夫すればいいんですね。

O(n^4)の方は

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + g;

が脳内でイメージ出来たときにおどろいた。こういうのって思いつかないと駄目なのか。

rate

996(-75)

2011-10-26

SRM 522 Div2

| 16:57

oox

250. PointErasingTwo / Passed System Test / 179

すべての場合を試すだけ。

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

int check[52][52];

class PointErasingTwo {
public:
  int getMaximum(vector <int> y) {
    int i, j, sz = y.size(), k, l;
    rep (i,52) rep (j,52) check[i][j] = 0;

    rep (i,sz) {
      check[y[i]][ i ] = 1;
    }

    int ans = 0;    
    rep (i,sz) {
      rep (j,sz) if (i != j) {
        int sx = min(i, j), sy = min(y[i], y[j]);
        int gx = max(i, j), gy = max(y[i], y[j]), cnt = 0;
        //printf("(%d,%d)->(%d,%d)\n", sx, sy, gx, gy);
        for (k = sx + 1; k < gx; ++k) {
          for (l = sy + 1; l < gy; ++l) {
            if (check[l][k]) cnt++;
          }
        }
        ans = max(ans, cnt);
      }
    }
    
    return ans;
  }
};

check[ y[i] ][i] = 1の部分をcheck[i][ y[i] ] = 1と書いた間違いに気づくまでにかなりかかり、点数ががが…

550. RowAndManyCoins / Passed System Test / 420

結局、初手で決められなければアリスの負けじゃないかという結論に

class RowAndManyCoins{
public:
  string getWinner(string cells) {
    int sz = cells.size();
    if (cells[0] == 'A' || cells[sz-1] == 'A') return "Alice";
    return "Bob";
  }
};

900. CorrectMultiplicationTwo / Failed System Test

勝手に問題を誤読してFailedした…。

調整された各A,B,Cに対しても、1以上10^6以下になるだろうと決め付けて全探索コードを出す…。

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

const int MAX_SZ = 1000000;

class CorrectMultiplicationTwo {
public:  
  int getMinimum(int a, int b, int c) {
    int i, j, ans = 1<<28;
    
    for (i = 1; i <= MAX_SZ; ++i) {
      for (j = 1; j <= MAX_SZ; ++j) {
        if (i * j > MAX_SZ) break;
        int C = i * j;
        ans = min(abs(a - i) + abs(b - j) + abs(C - c), ans);
      }
    }
    
    return ans;
  }
};

システムテストの(a,b,c) => (101, 9901, 1000000) で、恐らく最小になる組み合わせが(A,B,C) => (101, 9901, 1000001)で合計誤差が1なのだけど、if文でbreakしてるから誤差1の場合にansが更新されずに死んでた。

もちろん、MAX_SIZE = 1000001にすれば通るんだけど、これはあってるのか?

調整により生成されたCがMAX_SIZEを超えるような場合で、かつ誤差最小を満たす場合があるなら間違いなんだけど。。

でも、Div1はa,b,cの制約が1から10^9なので、Div2は全探索もおkってことなのかとか思ったり。。


rate := 1085 -> 1071

250ががが

2011-10-19

SRM 521 Div2

| 02:23

xox

250. RedAndGreen / Failed System Test

まぬけなミスで落とした。250は早解きの強迫観念に負けている…。

500. MissingParentheses / Passed System Test / 489

ICPC2011のB弱体化ばーじょん。

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

class MissingParentheses { 
public: 
  int countCorrections(string par) { 
    int i, sz = par.size(); 
    stack<char> s; 
    rep (i,sz) { 
      if (s.size() == 0) { 
        s.push(par[i]); continue; 
      } 
      if (par[i] == ')' && s.top() == '(') { 
        s.pop(); continue; 
      } 
      s.push(par[i]); 
    } 
    return s.size(); 
  } 
};

250のせいで微増…。

rate := 1074 -> 1085

2011-10-06

SRM 520 Div2

| 16:58

oox

250. SRMRoomAssignmentPhase / Passed System Test / 222

ソートして見る。

500. SRMCodingPhase / Passed System Test / 353

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

const int w[3] = { 2, 4, 8 }; 

class SRMCodingPhase { 
public: 
  int countScore(vector <int> points, vector <int> skills, int luck) { 
    int i, ans = 0; 
    for (int S=0; S<(1<<3); S++) { 
      int times = 0, tl = luck, tsum = 0;       
      rep (i, 3) if (S >> i & 1) times += skills[i]; 
      if (times - luck > 75) continue; 

      for (i=2; i>=0; i--) if (S >> i & 1) { 
        int cur_t = skills[i]; 
        if (tl > 0) { 
          if (tl >= cur_t) { tl -= cur_t-1; cur_t = 1;} 
          else { cur_t -= tl; tl = 0; } 
        } 
        tsum += points[i] - w[i]*cur_t; 
      } 

      ans = max(ans, tsum); 
    } 

    return ans; 
  } 
};

買う買わないのパターンをすべて試して、あとは得点の高い方からluckを振り分ける。

submitした後に迷ったけど大丈夫でした。

1000. SRMSystemTestPhase / Opened

途中..

rate := 963 > 1074

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>