SRM 538

Single Round Match 538 Round 1 - Division II:

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

2問提出して1問通過。269.02点。レートは958から995へ。緑コーダーを維持。Roomは45。Room内6位。

Problem Status Points
300 LeftOrRight Failed Sys. Test 0.0
500 EvenRoute 269.02 269.02
1050 SkewedPerspectives Opened 0.0
  • 2問提出して1問通過。300はシステムテストで落ちた。前回に続き目標を下回った
    • 300はTLE
    • 500は通ったが考察をしてみるにまぐれだったことが判明した(後述)
  • チャレンジできなかった
  • 前回から問題を読むと同時に条件や制限等を紙に書き出すようにしていることに気付いた
    • 理解できている問題ほどに書き出している傾向にあるようだ
    • 理解できていないと感じた問題ほどメモ量が少ない
  • 次回の目標
    • 確実2問に通す

LeftOrRight

問題を読むのに2分。実装とテストに10分。268.31/300.00を獲得したが、システムテストで落ちて0.00。

  • 総括
    • システムテストで落ちた
      • ラクティスルームで試してみるに、TLEとなるケースがあるようだ
      • 確かに自分の実装だと最悪2^50の組み合わせとなる。これは間に合わないだろう
      • 実装前に計算量を見積もらなかったのが間違い
    • あ、そうか。メモ化再帰にすればよかったのか
      • 全くすっぽ抜けていた。SRM終了後から3時間ほど気付かなかった
      • 再帰をメモ化再帰に直す行程は10分ほどであった
      • 現在位置が負の値を取るにも関わらずそのままメモ化していた
        • それでもテストを通ってしまった。恐ろしい不具合だ
  • コードリーディング
    • 全ての?をLとおいたシミュレーション結果と全ての?をRとおいたシミュレーション結果を比較する実装が多かった
      • 多勢に加勢する感覚か

提出した実装は以下(システムテストでTLEする)。

class LeftOrRight {
public:
  int maxDistance(std::string program) {
    return search(program, 0);
  };

  int search(std::string program, int d) {
    if (program.size() == 0)
      return std::abs(d);

    char command = program[0];

    if (command == 'L') {
      return std::max(search(program.substr(1), d - 1),
		      std::abs(d));
    }
    else if (command == 'R') {
      return std::max(search(program.substr(1), d + 1),
		      std::abs(d));
    }
    else {
      return std::max(std::max(search(program.substr(1), d - 1),
			       search(program.substr(1), d + 1)),
		      std::abs(d));
    }
  };

メモ化再帰にした実装は以下(システムテスト済)。

class LeftOrRight {
public:
  int maxDistance(std::string program) {
    program_ = program;

    memset((void*)memo_, -1, sizeof(memo_));

    return search(0, 0);
  };

  int search(int i, int j) {
    if (i == program_.size())
      return std::abs(j);

    if (memo_[i][j+50] >= 0)
      return memo_[i][j+50];

    char command = program_[i];

    if (command == 'L') {
      return memo_[i][j+50] = std::max(search(i + 1, j - 1),
				       std::abs(j));
    }
    else if (command == 'R') {
      return memo_[i][j+50] = std::max(search(i + 1, j + 1),
				       std::abs(j));
    }
    else {
      return memo_[i][j+50] = std::max(std::max(search(i + 1, j - 1),
						search(i + 1, j + 1)),
				       std::abs(j));
    }
  };

private:
  std::string program_;

  int memo_[50][101];
};

EvenRoute

問題を読んである程度理解するまでに15分。さらに考えること10分ほど。実装とテストに9分。269.02/500.00獲得。

  • 考察
    • ある点から出発し、マンハッタン幾何に乗っ取って移動する
      • 最後に元の点に戻るとすると、移動した総マンハッタン距離は必ず偶数となることに気付いた
      • 例題の一つを読んで気付いた
        • この例題がなければ気付かなかった(生涯気付かなかったかも。ありがたい)
    • この問題の場合、最後の点に訪れた後に元の点に戻ってこない
      • 最後の点から元の点までのマンハッタン距離を引いてやればよい
    • ...と思ってまず総距離を求める実装を行った
      • が、これは間違い
      • 総距離は訪れる点の順番によって変わる
      • まともに求めようとするとすごい組み合わせ量(n!)
      • 大きな偶数の数から偶数の数を引くか、奇数の数を引くかとして考えるのが妥当ではないか
      • 結局頭で整理できていなかったので復唱しよう
        • ある点から出発し、マンハッタン幾何に乗っ取って移動、最後に元の点に戻るとすると、移動した総マンハッタン距離はどのような経路を経たとしても必ず偶数となる
        • つまり元の点に戻ってくるのであれば、どのような順番で点群を訪れたとしても移動した総マンハッタン距離は必ず偶数となる
      • 考えると、この実装が通ったのはまぐれということになる
    • 問題を読んで、「総マンハッタン距離が奇数である経路を探す問題」なのか「移動する点間のマンハッタン距離に奇数のものが含まれている経路があるか」の何れを判定する問題なのか理解できなかった

提出した実装は以下。

class EvenRoute {
public:
  std::string isItPossible(std::vector<int> x, std::vector<int> y, int wantedParity) {
    int size = x.size();
      
    int l = manhatten(0, 0, x[0], y[0]) + manhatten(x[size-1], y[size-1], 0, 0);

    for (int i = 0; i < size - 1; i ++)
      l += manhatten(x[i], y[i], x[i+1], y[i+1]);

    for (int i = 0; i < size; i ++)
      if ((l - manhatten(0, 0, x[i], y[i])) % 2 == wantedParity)
	return "CAN";
    
    return "CANNOT";
  };

  int manhatten(int x1, int y1, int x2, int y2) {
    return std::abs(x2 - x1) + std::abs(y2 - y1);
  }
};

以下は考察を踏まえた後の実装(システムテスト済)。

class EvenRoute {
public:
  std::string isItPossible(std::vector<int> x, std::vector<int> y, int wantedParity) {
    for (int i = 0, size = x.size(); i < size; i ++)
      if ((std::abs(x[i]) + std::abs(y[i])) % 2 == wantedParity)
	return "CAN";

    return "CANNOT";
  };
};

SkewedPerspectives

30分あったので挑戦したが、解けなかった。0.00点。

  • メモ
    • 貪欲法とシミュレーションを合わせた方法で解くのかと思ったが、意外と難しい
    • 後で解く