Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-08-09

SRM446 Div1 Easy: CubeWalking

| 23:08 | SRM446 Div1 Easy: CubeWalking - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM446 Div1 Easy: CubeWalking - naoya_t@topcoder SRM446 Div1 Easy: CubeWalking - naoya_t@topcoder のブックマークコメント

提出版(こんなに書いてるから時間が無駄にかかる)

  • x,y座標を -1,0,1 で取っているのは % を使うのに面倒くさい(ので0,1,2で取ってるコードを見て!!!と思った)けれど、今回の場合は最後の判定が -1,0,1の方が(自分的に)直感的だったので良しとする
  • 30%無駄コードルールを気にして最初にいろいろ消してしまったので、repがなくてコンパイルエラーが出た
  • ていうか配列でいいだろx()とかy()とか何なの?馬鹿なの?死ぬの?
#define sz(a)  int((a).size())

class CubeWalking {
 private:
  int dir(int x,int y){
    switch(x){
      case 1: return 0;
      case -1: return 2;
      default: return (y==1)?1:3;
    }
  }
  int x(int d){
    switch(d){
      case 0: return 1;
      case 1: return 0;
      case 2: return -1;
      case 3: return 0;
    }
  }
  int y(int d){
    switch(d){
      case 0: return 0;
      case 1: return 1;
      case 2: return 0;
      case 3: return -1;
    }
  }
 public:
  string finalPosition(string movement) {
    int n=sz(movement);

    int dx=1,dy=0;
    int ox=0,oy=0;
    int d=0;
    for(int i=0;i<n;i++){
      switch(movement[i]){
        case 'L':
          d=(dir(dx,dy)+1)%4;
          dx=x(d); dy=y(d); break;
       case 'R':
          d=(dir(dx,dy)+3)%4;
          dx=x(d); dy=y(d); break;
        case 'W':
          ox+=dx;
          if (ox==2) ox=-1;
          else if (ox==-2) ox=1;
          oy+=dy;
          if (oy==2) oy=-1;
          else if (oy==-2) oy=1;
          break;
      }
    }
    if (ox*oy) return "RED";
    if (ox+oy) return "BLUE";
    return "GREEN";
  }
};

改良版:

  • 90度単位のベクトルの回転ぐらいライブラリ用意しとけ
  • pairの初期化はmake_pair不要><
  • pairの加減乗除ぐらいテンプレート書いておく
  • 負数の%の仕様が気に入らないならunsignedでキャストすればいいじゃない
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

template <typename T1, typename T2> pair<T1,T2> operator+=(pair<T1,T2>& p1, pair<T1,T2> p2)
{
  p1.first += p2.first; p1.second += p2.second; return p1;
}

pair<int,int> turn(pair<int,int> dir, int deg){
  if (deg < 0) deg = 360 - ((-deg)%360);
  deg %= 360;
  switch(deg){
    case 0: default:
      return dir;
    case 90:
      return make_pair(-dir.second, dir.first);
    case 180:
      return make_pair(-dir.first, -dir.second);
    case 270:
      return make_pair(dir.second, -dir.first);
  }
}

class CubeWalking {
 private:
 public:
  string finalPosition(string movement) {
    int n=sz(movement);
    pair<int,int> d(1,0), o(0,0);
    rep(i,n){
      switch(movement[i]){
        case 'L': d=turn(d,90); break;
        case 'R': d=turn(d,-90); break;
        case 'W': o+=d; break;
      }
    }
    int ox=((unsigned)o.first+1)%3-1;
    int oy=((unsigned)o.second+1)%3-1;
    if (ox*oy) return "RED";
    if (ox+oy) return "BLUE";
    return "GREEN";
  }
};

追記

  • 向きをd={0,1,2,3}で持っておいて、ox+=dx[d], oy+=dy[d]みたいにやるのが一番簡単そう…orz

pair同士の加減乗除テンプレート

| 23:08 | pair同士の加減乗除テンプレート - naoya_t@topcoder を含むブックマーク はてなブックマーク - pair同士の加減乗除テンプレート - naoya_t@topcoder pair同士の加減乗除テンプレート - naoya_t@topcoder のブックマークコメント

template <typename T1, typename T2> pair<T1,T2> operator+(pair<T1,T2> p1, pair<T1,T2> p2)
{
  return make_pair(p1.first+p2.first, p1.second+p2.second);
}
template <typename T1, typename T2> pair<T1,T2> operator+=(pair<T1,T2>& p1, pair<T1,T2> p2)
{
  p1.first += p2.first; p1.second += p2.second; return p1;
}

template <typename T1, typename T2> pair<T1,T2> operator-(pair<T1,T2> p1, pair<T1,T2> p2)
{
  return make_pair(p1.first-p2.first, p1.second-p2.second);
}
template <typename T1, typename T2> pair<T1,T2> operator-=(pair<T1,T2>& p1, pair<T1,T2> p2)
{
  p1.first -= p2.first; p1.second -= p2.second; return p1;
}

template <typename T1, typename T2, typename T3> pair<T1,T2> operator*(pair<T1,T2> p, T3 n)
{
  return make_pair(p.first*n, p.second*n);
}
template <typename T1, typename T2, typename T3> pair<T1,T2> operator*=(pair<T1,T2>& p, T3 n)
{
  p.first *= n; p.second *= n; return p;
}

template <typename T1, typename T2, typename T3> pair<T1,T2> operator/(pair<T1,T2> p, T3 n)
{
  return make_pair(p.first/n, p.second/n);
}
template <typename T1, typename T2, typename T3> pair<T1,T2> operator/=(pair<T1,T2>& p, T3 n)
{
  p.first /= n; p.second /= n; return p;
}

SRM446

03:00 | SRM446 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM446 - naoya_t@topcoder SRM446 - naoya_t@topcoder のブックマークコメント

08.08+.2009

黄色と青しかいない部屋。部屋で自分のレーティングがいちばん上だったのはDiv1では初めて。

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 CubeWalking passed - - 217.03
1 500 AntOnGraph 間に合わず - - -
1 1000 - -

250点問題: CubeWalking

  • そんなに難しい問題じゃない!
  • 11'25''はかかりすぎ

500点問題: AntOnGraph

  • 50x50全部つながってる場合に死ぬような方法しか思いつかなくて
  • 最後の15分で道筋が見えてきたが実装ぜんぜん間に合わない

1000点問題:

  • 開いてない!

Challenge Time

  • 誰も500点問題をsubmitしてない
  • 撃墜ゼロ

217.03点で室内6位。Div1全体では342/734位

  • 全問通してるのがEryx1人だけ

1582→1588 (+6) 微増

http://gyazo.com/e145de8d0c90bb5708a62a8101f41291.png

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