SRM 544 - Div I

Single Round Match 544 Round 1 - Division I

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

Problem Status Points
275 ElectionFraudDiv1 Unopened
500 FlipGame Passed System Test N/A
1000 SplittingFoxes Unopened
  • 練習
    • Div I Mediumがそんなに難しくないという話を聞いたので、挑戦した

FlipGame

http://community.topcoder.com/stat?c=problem_statement&pm=11974&rd=14736

  • 26分
    • 貪欲法を用いた
  • 左上から右下まで任意の最短経路を通る


  • 興味があるのは経路の左側だ
    • 太線の意味合いを最短経路から凸包とする


  • 経路の左側の数値を反転する


  • これを繰り返して全ての数値を0にする問題
  • 直感的に各行の数値のすぐ右側を通れば最適になりそうだ


  • 数値を反転する


  • 結果の範囲は確実に狭くなるはず

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

class FlipGame {
public:
  int minOperations(std::vector<std::string> board) {
    int h = board.size();

    for (int c = 0; ; c ++) {
      if (check(board))
	return c;
	  
      std::vector<int> tail;

      for (int x = 0, y = 0; y < h; y ++) {
	int pos = board[y].rfind('1');
	
	if (pos != std::string::npos) {
	  tail.push_back(x = std::max(x, pos + 1));
	}
	else {
	  tail.push_back(x);
	}
      }

      for (int y = 0; y < h; y ++)
	for (int x = 0; x < tail[y]; x ++)
	  if (board[y][x] == '0') {
	    board[y][x] = '1';
	  }
	  else {
	    board[y][x] = '0';
	  }
    }

    return -1;
  };

private:
  bool check(const std::vector<std::string>& board) const {
    EACH(it, board)
      if (it->find('1') != std::string::npos)
	return false;
    
    return true;
  };
};

  for ( int x=0; x<cx; x++ )
    board[y][x] ^= 1;
  • これはすごい
    • 全体的にも簡潔だ
  • XORは'A'と'B'、'a'と'b'では成立しないので注意が必要
    • すこし考えてみよう
    • 2と3を交互に入れ換える実装に近い
c = 'b' - c + 'a';
  • んー
    • よさそうだ