SRM 570 Div I

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15490

250に37分。チャレンジされ撃墜。レートは1474から1335へ。Room 21。

	Problem	Status	Points
250	RobotHerb	Challenge Succeeded	0.00
500	CentaurCompany	Opened	0.00
1000	CurvyonRails	Unopened

250に37分
- チャレンジされ撃墜
- 等号が足らず、境界条件に引っかかった
目標が不達成に終わった。悔しい
次回のSRMもしつこく「Div I Easyを奇麗な実装で提出する」を目標とする

RobotHerb

http://community.topcoder.com/stat?c=problem_statement&pm=12427&rd=15490&rm=315874&cr=22827765

37分。チャレンジされ撃墜された。

制約から、Tが[1, 10⁹]であった。愚直な実装だとTLEするように思えた

一先ず愚直な実装を行いアリーナで計測。TLEすることを確認

Tが4の倍数である場合は計算を圧縮できる。実装を変更し37分で提出した

境界条件を間違え、チャレンジで撃墜された

SRM後に失敗するケースを考えていたのだが思い浮かばず、@hotpepsi師匠にご教授いただいた

実行した後に元の方向に戻るプログラム(a = {4}、a = {1, 3}等)を4回繰り返したときに誤作動を起こす実装なのであった
師匠ありがとうございます

以下は修正した実装(システムテストをパス)。

class RobotHerb {
public:
  long long getdist(int T, std::vector<int> a) {
    long long dx, dy;
    int       dd;

    program(a, dx, dy, dd);

    long long x = 0, y = 0;
    int       d = dd;

    if (T >= 4) {
      simulate(dx, dy, dd, 4, x, y, d);

      x *= T / 4;
      y *= T / 4;
    }
    
    simulate(dx, dy, dd, T % 4, x, y, d);

    return std::abs(x) + std::abs(y);
  };

private:
  void program(const std::vector<int>& a, long long& x, long long& y, int& d) const {
    const long long dx[] = { 0, +1,  0, -1};
    const long long dy[] = {+1,  0, -1,  0};
    
    x = y = 0;
    d     = 0;
    
    for (int i = 0, size = a.size(); i < size; i ++) {
      x += dx[d] * a[i];
      y += dy[d] * a[i];
      
      d = (d + a[i]) % 4;
    }
  };

  void simulate(long long  dx, long long  dy, int dd, int T,
                long long&  x, long long&  y, int& d) const {
    
    for (int i = 0; i < T; i ++, d = (d + dd) % 4) {
      switch (d) {
      case 0:
        x += dx;
        y += dy;
        break;
      case 1:
        x += dy;
        y -= dx;
        break;
      case 2:
        x -= dx;
        y -= dy;
        break;
      case 3:
        x -= dy;
        y += dx;
        break;
      default:
        assert(false);
        break;
      }
    }
  }
};

SRM後、TopCoderでプログラムしてみた第1873回(TopCoder SRM570 直後放送) - Nico Liveを見ながら、@nico_shindanninさんの実装をコードリーディングする
- 簡潔だ。言葉にするのが難しいが、流れるような実装

@nico_shindanninさんの実装を参考にしながら初めから書き直す。実装がすっきりした

以下は書き直した実装(システムテストをパス)。

class RobotHerb {
public:
  long long getdist(int T, std::vector<int> a) {
    const long long dx[] = { 0, +1,  0, -1};
    const long long dy[] = {+1,  0, -1,  0};
    
    long long x = 0, y = 0;
    int       d = 0;

    int size = a.size();

    for (int t = 0; t < std::min(4, T); t ++)
      for (int i = 0; i < size; i ++) {
        x += dx[d] * a[i];
        y += dy[d] * a[i];
        
        d = (d  + a[i]) % 4;
      }

    if (T < 4)
      return std::abs(x) + std::abs(y);
  
    x *= T / 4;
    y *= T / 4;

    for (int t = 0; t < T % 4; t ++)
      for (int i = 0; i < size; i ++) {
        x += dx[d] * a[i];
        y += dy[d] * a[i];
        
        d = (d  + a[i]) % 4;
      }

    return std::abs(x) + std::abs(y);
  };
};