naoya_t@topcoder

SRM446 Div1 Easy: CubeWalking

過去問, 練習 | 23:08 |

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

• 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同士の加減乗除テンプレート

library | 23:08 |

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 |

08.08+.2009

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

DIV	level	問題名	競技中	後で	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位

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

1582→1588 (+6) 微増