naoya_t@topcoder

Marathon Match 56: EnclosingCircles (MM初参加)

Marathon Match | 03:14 |

• 終了まで26時間しか残ってないけど参加
• やり方わからないけど、とりあえずコード書いて投稿してみるテスト

実戦

• １投目。まずは大雑把にグループ分けして、rectangleを囲む大きめの円を描くやつを投げる。15932.14点
• ２投目。それではあんまりなので、凸包を求め（るところまでは出来たが）、それを包む円を（どう求めたらいいのかと悩み、rectangleの中心はそのままでいちばん遠い点を通る円を描くやつをまず投げようと試みる。が投稿を待たされる。24683.39点。１時間に１回しか投稿できないのか..と嘆いてたら２時間に１回だと事実を突きつけられた。にょろーん
• ３投目。いちばん遠い点の方向へ中心を移動させ、円を２つめの点が乗るまで小さくしていく辺り。27833.71点
• ４投目。点が乗っていない180度より長い弧がある場合にさらに小さくできる辺り。24553.59点。円の計算精度が上がって得点アップのはずが（予想に反し）３回目のよりも悪い結果になったorz
• ５投目。３投目のをもう一度サブミット。27833.71点
• 時間切れ。
• 123位

教訓

• 凸包を包む最小の円を描くアルゴリズムはもっといいのがある
  • が、問題はそこではない
  • 焼きなまし法…
• 最初から出たほうがいい。２時間に１投しかできないがやりたい事は沢山出てくる
• いつ投稿してもchokudai先生のがテスト中。いつ寝てるんだろう
• マラソン楽しいです！

10/22追記

長いPendingの後の長いSystem Test（２日ほどかかってた）が終わり結果が出た。

Rank: 131

Provisional Score: 27833.71

Final Score: 65580.07

Rating: 1156

Volatility: 385

... 緑からのスタートか... orz

同追記２

さっき見たらレーティング0になってた。白文字で。White coder...（おそらくTopCoderが壊れてる）

SRM beta (Member Pilot 2)

15:33 |

09.29+.2009

続きを読む

SRM beta 2 Div1 Easy: TwistedMatrix

過去問, 練習 | 11:13 |

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

ll ubin(const string& s){
  ll n=0LL;
  for (int i=0,c=sz(s); i<c; i++){
    n = (n<<1LL) | (s[i]=='1'?1:0);
  }
  return n;
}
vector<ll> lex(const vector<string>& A){
  int n=sz(A);
  vector<ll> v(n,0LL);
  rep(i,n){
    v[i] = ubin(A[i]);
  }
  return v;
}
vector<string> turn(const vector<string>& A,int xmin,int ymin,int dir){
  vector<string> At(all(A));
  switch(dir){
    case 1: // cw
      At[ymin][xmin]     = A[ymin+1][xmin];
      At[ymin][xmin+1]   = A[ymin][xmin];
      At[ymin+1][xmin]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin+1] = A[ymin][xmin+1];
      break;
    case -1: // ccw
      At[ymin][xmin]     = A[ymin][xmin+1];
      At[ymin][xmin+1]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin]   = A[ymin][xmin];
      At[ymin+1][xmin+1] = A[ymin+1][xmin];
      break;
  }
  return At;
}

class TwistedMatrix {

 public:
  int d(int c1, int c2){ /// これは使ってないよ
    if (c1==c2) return 0;
    if (c2=='?') return 9;
    return c2-c1;
  }

  int N, M;
  
  int diff(const vector<string>& A, const vector<string>& B){
    int cnt = 0;
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?' || B[n][m]=='?') continue;
        if (B[n][m]!=A[n][m]) cnt++;
      }
    }
    return cnt;
  }
  vector<string> zero(const vector<string>& A){
    vector<string> z(all(A));
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?') z[n][m] = '0';
      }
    }
    return z;
  }
  
  vector <string> solve(vector <string> A, vector <string> B) {
    N=sz(A);
    M=sz(A[0]);

    vector<ll> minlex(N, (1LL << M) - 1LL);
    vector<string> ans(0);
    
    rep(n,N-1){
      rep(m,M-1){
        vector<string> At1 = turn(A,m,n,1);
        if(diff(At1,B)==0) {
          if (lex(At1) < minlex){
            ans = zero(At1);
            minlex = lex(At1);
          }
        }
        vector<string> At2 = turn(A,m,n,-1);
        if(diff(At2,B)==0) {
          if (lex(At2) < minlex){
            ans = zero(At2);
            minlex = lex(At2);
          }
        }
      }
    }
    return ans;
  }
};

int ubin(const string& s){
  int n=0;
  for (int i=0,c=sz(s); i<c; i++){
    n = (n<<1) | (s[i]=='1'?1:0);
  }
  return n;
}
vector<int> lex(const vector<string>& A){
  int n=sz(A);
  vector<int> v(n,0);
  rep(i,n){
    v[i] = ubin(A[i]);
  }
  return v;
}
vector<string> turn(const vector<string>& A,int xmin,int ymin,int dir){
  vector<string> At(all(A));
  switch(dir){
    case 1: // cw
      At[ymin][xmin]     = A[ymin+1][xmin];
      At[ymin][xmin+1]   = A[ymin][xmin];
      At[ymin+1][xmin]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin+1] = A[ymin][xmin+1];
      break;
    case -1: // ccw
      At[ymin][xmin]     = A[ymin][xmin+1];
      At[ymin][xmin+1]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin]   = A[ymin][xmin];
      At[ymin+1][xmin+1] = A[ymin+1][xmin];
      break;
  }
  return At;
}

class TwistedMatrix {
  int N, M;

 public:
  int diff(const vector<string>& A, const vector<string>& B){
    int cnt = 0;
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?' || B[n][m]=='?') continue;
        if (B[n][m]!=A[n][m]) cnt++;
      }
    }
    return cnt;
  }

  vector<string> zero(const vector<string>& A, const vector<string>& B){
    vector<string> z(all(A));
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?') {
          z[n][m] = (B[n][m]=='?') ? '0' : B[n][m];
        }
      }
    }
    return z;
  }
  
  vector <string> solve(vector <string> A, vector <string> B) {
    N=sz(A);
    M=sz(A[0]);

    // vector<ll> minlex(N, (1LL << M) - 1LL);
    vector<int> minlex(N, (1 << M));
    vector<string> ans(0);
    
    rep(n,N-1){
      rep(m,M-1){
        for(int dir=-1;dir<=1;dir+=2) {
          vector<string> At = turn(A,m,n,dir);
          if(diff(At,B)==0) {
            vector<string> tmp = zero(At,B);
            vector<int> la = lex(tmp);
            if (la < minlex){
              ans = tmp;
              minlex = la;
            }
          }
        }
      }
    }
    return ans;
  }
};

Google Code Jam: Round 2 (2.5hrs)

13:54 |

結果：11点、1768位、TシャツGETならず。

続きを読む

SRM449

02:10 |

09.23+.2009

続きを読む

Google Code Jam: Round 1C (2.5hrs)

19:25 |

• 9/13 18:00JST〜
• PRML hackathon #1の最中でしたが A,B を解いてみました
• watch onlyでデータセットはダウンロード出来ないのでただ解くだけ

続きを読む

Google Code Jam: Round 1B (2.5hrs)

11:13 |

• 9/13 1:00am (JST)〜
• 1Aで落ちてたらいけないので、一応1amに待機していた
• 参加できない (watch only)
• でも問題は見れるので解くよ
• A と B まで解いて１時間弱

続きを読む