SRM466 Div1

ケガからの復帰戦.一つも解けなかったけど撃墜成功してdiv1残れた.わーい.

250 LotteryCheating

  • 文字をそんなにたくさん書き換えなくても答えに行くんじゃないかなぁと思って探索してみた.
  • 答えをみると最大5なので,大間違いではない.間違いだけど.
  • 手元でいくつか試してみたらTLEになるケースを発見.
  • いくつか高速化してみたけど全然間に合わない.
  • 約数が奇数の数字を最初に求めて,そこに変換してみる方法かなぁと思った.
  • でも2 ^ 32個の候補を最初に調べるわけにいかないし…
    • ここで約数奇数の法則性を探しに行くことが正解への分かれ道だったのだろうか.
  • でも,自分と同じく探索しようとした人は自分がTLEになるサンプルで落とせた.2撃墜.

id:halwhiteさんに探索と思ってはいけないと思うって怒られた(´・ω・`)ショボーン

500 LotteryPyaterochka

  • 見た感じ解ける気がするー.
  • でも250が解けてないので,普段解けない500を行くべきかとゆっくり考えられず.
  • とりあえずチケットは1 2 3 4 5 6 ... と順番に並んでると考えても全く同じことだとわかった.
  • で,あとはwinning numberが一行三つ以上になる並び方…こんがらかってきて250へ戻る.受験生なら解けたよ.きっと.

方針としては,winning numberが5行,4行のときと3行の一部の時はwinnerになれないということを計算する.あとで書いたらかなりシンプルだった.

class LotteryPyaterochka {
public:
  long long nCr(long long N,long long r){
    if (N < r) return 0;
    long long ret = 1LL;
    REP(i,r)
      ret *= N-i;
    REP(i,r)
      ret /= (i+1);
    return ret;
  }
  double chanceToWin(int N) {
    return 1.0 - (double)(nCr(N,5)*5*5*5*5*5+
                          nCr(N,4)*4*nCr(5,2)*5*5*5 +
                          nCr(N,3)*3*nCr(5,2)*nCr(5,2)*5)/nCr(N*5,5);
    
  }
}

long longにしないと桁あふれするみたい.こういうミスはよくやるので気を付けたい.

1000

未読.500が解けないと,ねぇ…


結果 x x x 2撃墜 100 1247 -> 1268


微増.思えばブログ作っていきなり怪我したのでtopcoder初参戦記だったり.