SRM 550 Div II

Single Round Match 550 Round 1

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

250に6分。550に1時間ほどかけ、完成しなかった。合計239.48点。レートは1097から1096へ微減。緑コーダー。Room 76

Problem Status Points
250 EasyConversionMachine System Test Passed 239.48
550 RotatingBot Opened 0.00
1000 TopView Unopened
  • 250に6分。239.48点
  • 500に1時間ほどかけ、完成しなかった
  • 次回の目標
    • 2問通す

EasyConversionMachine

http://community.topcoder.com/stat?c=problem_statement&pm=12125&rd=15172

6分。239.48点。

  • 最低何手必要か算出する
    • 与えられた手数が必要な手数に足りない場合は不可能
    • 与えられた手数が余ってしまった場合は、2n回の無駄な入れ替えを続ければよい
      • つまり、必要な手数と与えられた手数の偶奇が等しければよい

実装は以下(システムテスト済)。

class EasyConversionMachine {
public:
  std::string isItPossible(std::string originalWord, std::string finalWord, int k) {
    int c = 0;

    for (int i = 0, size = originalWord.size(); i < size; i ++)
      if (originalWord[i] != finalWord[i])
	c ++;

    if (k < c)
      return "IMPOSSIBLE";

    if (k % 2 == c % 2) {
      return "POSSIBLE";
    }
    else {
      return "IMPOSSIBLE";
    }
  };
};
  • 今考えるに、必要な手数と与えられた手数の差が2の倍数であるかどうかを判断したほうがよかったように思える
    • 与えられた手数をk、必要な手数をcとすると

これを反映した実装は以下(システムテスト済)。

class EasyConversionMachine {
public:
  std::string isItPossible(std::string originalWord, std::string finalWord, int k) {
    int c = 0;

    for (int i = 0, size = originalWord.size(); i < size; i ++)
      if (originalWord[i] != finalWord[i])
	c ++;

    if (k >= c && (k - c) % 2 == 0) {
      return "POSSIBLE";
    }
    else {
      return "IMPOSSIBLE";
    }
  };
};

RotatingBot

http://community.topcoder.com/stat?c=problem_statement&pm=12033&rd=15172

1時間かけて時間切れ。システムテストの5番を理解できたのが終了15分ほど前で、実装が間に合わなかった。

  • 普通に実装した
    • システムテストの5番以外は通った
    • {8, 6, 6, 1}が何故-1を返すか全く理解できなかった
  • SRM中に以下のような図を書いた


  • SRM後、丁寧に書くと分かりやすいことに気付いた


  • 以下の色の濃いグリッドに着眼しよう


  • ロボットは右上のグリッドから左の方向に進む
    • 方向転換した場所の左側にはまだ訪れていないグリッドがある
    • つまり、方向転換する理由がない。そのためこの経路は無効と判定しなければならない
  • 実装の詳細を考えよう
  • movesの要素数が1つの場合は簡単


  • 素数が2つの場合も同様


  • 素数が3つ以上場合には台形のような形になる
    • 上辺と下辺の長いほうが水平方向の辺の長さになる
    • 以下の場合、水平方向の辺の長さは8だ


    • 以下の場合も水平方向の辺の長さは8だ


  • movesの要素数が4以上の場合はシミュレーションをして、経路の有効性をチェックする
  • グリッドからはみ出す経路は無効
  • すでに訪れたグリッドに再訪する経路も無効だ


  • さらに、次のグリッドに進むことができるのに方向転換するような経路も無効だ


  • マニュアルで止まる場合があるため最後のmovesのチェックはしなくてもよい

以下はSRM終了後に行った実装(システムテスト済)。

const int dx[] = {1, 0, -1,  0};
const int dy[] = {0, 1,  0, -1};


class RotatingBot {
public:
  int minArea(std::vector<int> moves) {
    int size = moves.size();

    if (size == 1) {
      return moves[0] + 1;
    }
    else if (size == 2) {
      return (moves[0] + 1) * (moves[1] + 1);
    }
    else if (size == 3) {
      return (std::max(moves[0], moves[2]) + 1) * (moves[1] + 1);
    }
    else {
      int w = std::max(moves[0], moves[2]) + 1;
      int h = std::max(moves[1], moves[3]) + 1;

      int x = (moves[0] > moves[2]) ? 0 : w - 1 - moves[0];
      int y = (moves[1] > moves[3]) ? 0 : h - 1 - moves[1];

      std::set<std::pair<int, int> > set;

      set.insert(std::make_pair<int, int>(x, y));
      
      for (int i = 0; i < size; i ++) {
	for (int j = 0; j < moves[i]; j ++) {
	  x += dx[i % 4];
	  y += dy[i % 4];

	  if (0 <= x && x < w && 0 <= y && y < h) {
	    std::pair<int, int> pair(x, y);
	  
	    if (set.count(pair))
	      return -1;
	  
	    set.insert(pair);
	  }
	  else {
	    return -1;
	  }
	}

	if (2 <= i && i < size - 1) {
	  if ((0 < x && x < w - 1) || (0 < y && y < h - 1))
	    if (! set.count(std::make_pair<int, int>(x + dx[i % 4], y + dy[i % 4])))
	      return -1;
	}
      }

      return w * h;
    }
  };
};
  • うーん
    • 皆どう実装しているのだろう
  • SRM 550 Div1 - minus9dの記録を読む
  • 方向転換した要因をマークしつつシミュレーションを行い、最後にまとめて整合性をチェックする
    • 順次整合性をチェックするよりも明快な実装となる
  • 以下は有効な経路とマークの例


  • 以下は無効な経路とマークの例