Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-12-23

SRM456 Hard: FunctionalEquation

| 17:38 | SRM456 Hard: FunctionalEquation - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 Hard: FunctionalEquation - naoya_t@topcoder SRM456 Hard: FunctionalEquation - naoya_t@topcoder のブックマークコメント

寝る前にちょっと考えた

  • f(x)=ax+b な形だとa=1,b=(C-1)/2になってしまってCが偶数のときにf(x)がintegerにならなくてアウト
  • f(x)=ax^2 + bx + c な形だとa=0で結局同上
  • f(x)=Σa_ix^i で考えると... 寝落ち

SRM456 Medium: CutSticks

| 20:46 | SRM456 Medium: CutSticks - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 Medium: CutSticks - naoya_t@topcoder SRM456 Medium: CutSticks - naoya_t@topcoder のブックマークコメント

  • なんか最初単峰性の何かを想像してて、どこで最大になるか求めようとしていた
  • 既存の棒の長さを順番に試していって、どこまで行けるか(というか求める値がどことどこの間か)という問題に脳内修正
  • ということは要は任意の値でどこまで行けるか、に脳内修正
  • ま、二分探索さ。最初から分かっていたさw
  • どこまで「何が」行けるかの計算に悩んでてごにょごにょしてるうちに時間切れ
  • Challenge Phase無視
  • Practice room
    • 最初の棒の本数(N)が多いときに変な値が出る → 二分探索の最小値が小さすぎて、割り算した結果がINT_MAXより大きくなる → 無限大表現に INT_MAX/N を使うか(※素直にlong longにしとけばいいものを)
    • 最初の本数が少ないときに小さい値が出る → 大きい棒を切ることで順位が変わるのにstick[K](※並べ替え済)を返していた。お馬鹿
    • Cが大きいときに変な値が出る →そろそろlong longにしないと無理ですか
    • 答えが1e8みたいに大きくなる時に二分探索が止まらない → 終了条件がhi-lo>1e-9とか駄目ですってば
    • 5度目の正直でpassed
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);var++)
#define sz(a)  int((a).size())

class CutSticks {
  ll N, C, K;
  vector<double> s;  
 public:
  int f(double x){
    ll cutcnt=0,sum=0;
    rep(j,N){
      double sx = s[j]/x;
      ll cut;
      if (sx >= (double)INT_MAX) cut = INT_MAX;
      else cut=(ll)sx;
      if (cut==0) continue;
      if (cut>=2) cutcnt+=(cut-1);
      if (cut>=1) sum+=cut;
    }
    if (cutcnt >= C) sum -= cutcnt-C;
    if (sum>=K) return 1;
    return 0;
  }
  double md(double l, double h) {
    if (!f(l)) return -1;
    if (f(h)) return h; //-2;
    double m=(l+h)/2;
    if ((h-l)/h < 1e-12) return m;
    if (f(m)) return md(m,h);
    else return md(l,m);
  }
  double maxKth(vector<int> sticks, int c, int k) {
    N=sz(sticks); C=c; K=k;
    sort(all(sticks)); reverse(all(sticks));
    s.resize(N); rep(i,N) s[i]=(double)sticks[i];
    return md(1e-12,s[0]);
  }
};

SRM456 Easy: SilverDistance

| 20:46 | SRM456 Easy: SilverDistance - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 Easy: SilverDistance - naoya_t@topcoder SRM456 Easy: SilverDistance - naoya_t@topcoder のブックマークコメント

  • 45度傾けたら超簡単だった
  • 格子点以外への行き方が1通りしかない
  • マンハッタン距離 + 格子点でなければ+1
class SilverDistance {
 public:
  int minSteps(int sx, int sy, int gx, int gy) {
    int dx = gx-sx, dy = gy-sy;
    if (dx==0&&dy==0) return 0;
    int up=0;
    int ex =  dx+dy;
    int ey = -dx+dy;
    if (ex&1) {
      up=1; ex--; ey--;
    }
    int hx = ex/2, hy = ey/2;
    return abs(hx)+abs(hy)+up;
  }
};

こんな問題で悩むなんて… orz

SRM455 Easy(300): DonutsOnTheGridEasy

| 22:00 | SRM455 Easy(300): DonutsOnTheGridEasy - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM455 Easy(300): DonutsOnTheGridEasy - naoya_t@topcoder SRM455 Easy(300): DonutsOnTheGridEasy - naoya_t@topcoder のブックマークコメント

  • 問題激しく読み違えてた...ドーナツが幾つ取れるか数えようとしてた。重箱状の階層の深さの最大を求めるだけだった。
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)

// memoize..
char z[50][50][51][51], mp[50][50][51][51];

class DonutsOnTheGridEasy {
  vector<string> gr;
  int R,C;
  
  int isZeroShape(int r,int c,int h,int w){
    if (h<3 || w<3) return 0;
    if (z[r][c][h][w]>=0) return z[r][c][h][w]; // memo

    int re=1;
    
    rep(j,h) { int y=r+j;
      if (gr[y][c]=='.') {re=0; goto end;}
      if (gr[y][c+(w-1)]=='.') {re=0; goto end;}
    }
    rep(i,w) { int x=c+i;
      if (gr[r][x]=='.') {re=0; goto end;}
      if (gr[r+(h-1)][x]=='.') {re=0; goto end;}
    }
 end:
    return z[r][c][h][w] = re;
  }

  int sub(int r,int c,int h,int w){
    if (h<3 || w<3) return 0;
    if (mp[r][c][h][w]>=0) return mp[r][c][h][w]; // memo

    int ct=0; if (isZeroShape(r,c,h,w)) ct=1+sub(r+1,c+1,h-2,w-2);
    FOR(hj,1,h-1) ct = max(ct, max(sub(r,c,hj,w),sub(r+hj,c,h-hj,w)));
    FOR(wj,1,w-1) ct = max(ct, max(sub(r,c,h,wj),sub(r,c+wj,h,w-wj)));

    mp[r][c][h][w] = ct;
    return ct;
  }
 public:
  int calc(vector<string> grid) {
    R=sz(grid), C=sz(grid[0]);
    gr = grid;

    // clean up
    memset(z,255,sizeof(z)); memset(mp,255,sizeof(mp));

    return sub(0,0,R,C);
  }
};

SRM456

13:53 | SRM456 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 - naoya_t@topcoder SRM456 - naoya_t@topcoder のブックマークコメント

12.23.2009

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 SilverDistance 諦めたので試合終了 - -
1 450 CutSticks 間に合わず - - -
1 1050 - 開いてない -

250点問題: SilverDistance

  • 駒移動系苦手意識++
  • mapでバグって悩んで
  • 結論から言うと空のpriority_queueからtop()取ろうとしてた
  • てか何探索しようとしてるの... うまく行ってもTLEな予感
  • 40分使っちゃったので諦めて450点問題へ

450点問題: CutSticks

  • なんで小数が出る
  • 二分探索とか最急降下とか?
  • 求めるのは山の頂点ではなく、長さどこまで行けるかの境界値。だったら二分探索だよな
  • 最初、どことどこの間だろうか、とか既存の棒の長さで考えてた
  • でも任意の長さでいいわけで
  • 時間切れ
  • Practice roomにて5度目の正直でpassed
    • int -> long long にすれば解決する問題多し
    • 数値がでかくなると差分1e-9で終了しないとかよくあるよね
    • あとで書く

1050点問題:

  • 開いてない

Challenge Time

  • 450点問題考えてた

System Test

結果

  • 0点, xxx/yyy位
  • 1353→1292 (-61)

下落の一途…もうだめぽ

http://gyazo.com/c331442a3e26e3b97408b12938703412.png

rng_58rng_582009/12/24 19:36C = 2 のとき、奇数なら1を足す関数
f(x) = x + ((x%2 == 0) ? 0 : 1)
とかが条件を満たします

n4_tn4_t2009/12/25 11:49問題作成者様直々にコメントありがとうございます!!
なるほどそういうのもアリですね。頭固かったです。

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091223