日本人いっぱい

TopCoder


定員1500人を超えたとかで参加できない人もいるみたい。


500点問題をなんども間違っていないかテストしたりテストケース追加したりしたんだけど、これ与えられているテストケースがコーナーケースじゃないの。さっさとサブミットしてしまった方がよかったのかなぁ。そして残り10分でC++で幅優先探索のコードを書く力量は僕にはない。今後の課題にする。


このあと一人だけ1000点を解いた。僕4位だからダメ元で迎撃する。

ダメ元で迎撃しようと用意しておいたテストケースを貼ろうとしたらそうだったコピペできないんだった。なれないGUIでテストケース作ってたら誰かに先に撃墜されてた。

なんか2位。練習に1位の人を攻撃してみよう。

。。。なんか間違いを犯した気がする。チャレンジ失敗のペナルティで3位と逆転したっぽい。


システムテストの結果：

先生、うちのクラスは500点問題全滅なんですけど＞＜


まぁ、理由はだいたい想像がつくが。うーむ。どういう戦略が正解だったのかなぁ。

        • -

500点問題の解説。ある数が与えられたときに、その数が「素数のn乗」であるかどうかを判定せよ、という問題。nは2以上。返す値は、素数のn乗ではないとき空のvector、pのn乗であるとき{p, n}。これで与えられる数の範囲が狭ければまだいいが、恐ろしいことに「与えられる数は2以上10^18以下とする」とな。引数が文字列で与えられるからてっきりlong longに収まらないと思い込んでしまったが、収まるよね。

>>> 2 ** 63
9223372036854775808L
>>> 10 ** 18
1000000000000000000L

探すべき空間が広いので、順番に探したりしたら全然間に合わない。というわけでpow(x, 1.0/3.0)とかしてみた。xがなんらかの整数のn乗であるかどうかは、pow(x, 1.0 / n)の値を切り捨ててプラスマイナス1くらいの範囲でn乗してみてxと一致するかどうかをチェック。

  vector <int> baseAndExponent(string n) {
    LL v = lexical_cast<LL>(n);
    for(size_t i=2; i<10000; i++){
      double d = pow(v, 1.0/i);
      if(d < 2.0) break;
      cout << d << endl;
      LL start(d - 1);
      LL end(d + 2);
      for(size_t j=start; j<end; j++){
	LL power = 1;
        for(size_t k=0; k<i; k++){
	  power *= j;
	}
	if(power == v){
	  // is prime?
	  bool isPrime = true;
	  LL ubound(sqrt(j)+1);
	  for(size_t x=2; x<ubound; x++){
	    if(j % x == 0){
	      isPrime = false;
	      break;
	    }
	  }
	  if(j < 4) isPrime = true;
	  if(isPrime){
	    vector<int> result;
	    result.push_back(j);
	    result.push_back(i);
	    return result;
	  }
	}
      }
    }
    vector<int> result;
    return result;
  }

浮動小数点数の切り捨ての仕方がわからないのでwarningを無視してむりやり整数に。システムテストに落ちた原因はここ

	LL power = 1;
        for(size_t k=0; k<i; k++){
	  power *= j;
	}
	if(power == v){

「jをk乗して、vに一致するなら」のつもりだったけども、これが入力が639558602475808609の時に2.07952の56乗になって、プラス1の3の56乗がオーバーフローを繰り返した結果なんと入力に一致するという罠。

3
9
27
81
243
729
2187
(snip)
6048575297968530377
-301018179803960485
-903054539411881455
-2709163618235644365
-8127490854706933095
-5935728490411247669
639558602475808609

うあー。オーバーフローの可能性にもっと敏感にならなきゃ行けないんだなぁ。
気づいていれば「if(power < 0) break;」の一言で一位になれたんだけどな。まだまだ道のりは長い。

        • -

次回の目標
□ 500点問題を取る
□ 掛け算、足し算を見たらオーバーフローを疑え