TopCoder SRM495 Div1

ぶっとんだ配点。

275

1からNまでの整数の書かれたカードがあり、色は素数なら赤、そうでなければ青になっている。今、色だけがわかっている。カードの数を特定できるだけ特定せよ。

全探査でやったら計算量実は危なかったかもしれないけど通った

500

N個の箱があり、どれか一つの箱を除いて人参が入っている。人参が入っていない確率はどの箱も同じである。ある箱を開けると、その箱を含めたいくつかの箱の情報（中に人参が入っているか否か）がわかる。空箱を開けずに、空箱を判定することができる確率を求めよ。

N-1個の頂点を被覆するような最小の頂点数を求める。強連結成分分解をするとできる。greedyでやってる人がけっこういてことごとく落ちてた

975

どの2つのエレベーターの間の間隔も常に一定であり、同じ階には複数のエレベーターは止まらないようないくつかのエレベーターがある。H階、N台のエレベーターのとき、エレベーターは何通り考えられるか。

どんな値を求めればいいかはだいたいわかったけど求められない

結果

275と500は通った。500でgreedyでやってる人(system test failedしてた)を落としたかったけどテストケースが思いつかなかった。

oox 534.89 21位

Rating: 2304 -> 2401