SRM 438

Single Round Match 438 Round 1 - Division II

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

練習。250に12分ほど。一点見落とし、WA。500に20分ほど。こちらも見落としがあり、WA。全敗だった。

Problem Status Points
250 UnluckyNumbers Opened WA
500 FeudaliasBattle Opened WA
1000 EndlessStringMachine Unopened
  • 250に12分ほど
    • 簡単だった
    • しかし、条件を見誤った
  • 500に20分ほど
    • こちらも簡単だった
    • しかし、距離を求めるの際にintの乗算でオーバーフローを起こした
    • 負の値に対してsqrtを取ったらしく、結果がNaNとなるテストケースがあった

UnluckyNumbers

12分ほど。システムテストに落ちた。

  • ある数値nが素な数値の集合の区間に挟まっているのかどうか調べる
    • ある区間に挟まっているのであれば、その中に作り得る区間の中で数値が挟まれているものの数を求める
    • そうでなければ、0を返す
  • 簡単だった
    • コーナーケースに注意を払う余裕もあった
    • 数値の集合の最小値よりも小さい範囲と最大値よりも大きな範囲を考慮すべきかチェックした
    • 例題にそのようなケースはなかった
  • ある数値nが1から集合の最大値までであるという条件を見逃してしまった
    • 言い換えれば、「数値の集合の最小値よりも小さい数値n」が与えられることがある、ということなのであった
      • SRM 541では例題でのみ判断出来るケースがあったが、この場合は条件のみで判断できるケースであった
  • 投稿して、システムテストに落ちた
  • 実装を見直す
    • 整列する前に集合に0を入れた

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

class UnluckyNumbers {
public:
  int getCount(std::vector<int> luckySet, int n) {
    luckySet.push_back(0);

    std::sort(ALL(luckySet));

    for (int i = 0, size = luckySet.size(); i < size - 1; i ++)
      if (luckySet[i] < n && n < luckySet[i + 1]) {
	int c = 0;

	for (int j = luckySet[i] + 1; j < luckySet[i + 1]; j ++)
	  for (int k = j + 1; k < luckySet[i + 1]; k ++)
	    if (j <= n && n <= k)
	      c ++;

	return c;
      }
    
    return 0;
  };
};

FeudaliasBattle

20分ほどで完成。システムテストに落ちた。

  • 簡単だった
    • 素直に全ての場合を計算して比較した
  • 距離を算出する関数内でintがオーバーフローするような演算を行ってしまった
    • 大きな値の乗算が原因であった
    • 結果が負値となってしまったようだ
    • その値をsqrtして、結果がNaNとなってしまった
  • 実装を見直す
    • doubleにキャストしてから乗算を行った

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

class FeudaliasBattle {
public:
  double getMinimumTime(std::vector<int> baseX, std::vector<int> baseY, std::vector<int> siloX, std::vector<int> siloY, int takeOffTime, int rechargeTime, int missileSpeed) {
    double d00 = distance(siloX[0], siloY[0], baseX[0], baseY[0]);
    double d01 = distance(siloX[0], siloY[0], baseX[1], baseY[1]);
    double d10 = distance(siloX[1], siloY[1], baseX[0], baseY[0]);
    double d11 = distance(siloX[1], siloY[1], baseX[1], baseY[1]);

    double t00 = std::min(std::max(takeOffTime / 60.0                                     + d00 / missileSpeed,
				   takeOffTime / 60.0 + rechargeTime + takeOffTime / 60.0 + d01 / missileSpeed),
			  std::max(takeOffTime / 60.0                                     + d01 / missileSpeed,
				   takeOffTime / 60.0 + rechargeTime + takeOffTime / 60.0 + d00 / missileSpeed));

    double t01 = std::max(takeOffTime / 60.0 + d00 / missileSpeed,
			  takeOffTime / 60.0 + d11 / missileSpeed);

    double t10 = std::max(takeOffTime / 60.0 + d01 / missileSpeed,
			  takeOffTime / 60.0 + d10 / missileSpeed);

    double t11 = std::min(std::max(takeOffTime / 60.0                                     + d11 / missileSpeed,
				   takeOffTime / 60.0 + rechargeTime + takeOffTime / 60.0 + d10 / missileSpeed),
			  std::max(takeOffTime / 60.0                                     + d10 / missileSpeed,
				   takeOffTime / 60.0 + rechargeTime + takeOffTime / 60.0 + d11 / missileSpeed));
    
    return std::min(t00, std::min(t01, std::min(t10, t11)));
  };

public:
  double distance(double sx, double sy, double bx, double by) const {
    return sqrt((bx - sx) * (bx - sx) + (by - sy) * (by - sy));
  };
};