Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2010-07-08

[]SRM475 00:34 はてなブックマーク - SRM475 - TopCoderの学習のお時間

2010-07-07 20:00-(JST

http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14156&rm=305142

300-600-900 という嫌な感じのする配点


Levelタイトル試合中あとでひとこと
300RabbitSteppingAC 19min-とりあえず書けば通るのだが…
600RabbitIncreasingCompiled-近親相姦ヤバい
900RabbitProgrammingOpened-900だけども当然のようにむずい

  • Coding
    • 300
      • 問題文長い…頑張って読む
      • Nが最大17ということは単純にシミュレーションすれば間に合う。300なのは面倒だからなのか?
      • 書く
      • 一発ではサンプル通らなかったがちょこちょこバグ直すと通ったので提出
      • 後で、偶奇だけ見るというきれいな解法を聞いて感心する
    • 600
      • サイズ1000万ということは線形でもいいのか。珍しい
      • 規則がよくわからないので具体的に書き出してみる
      • フィボナッチ数が見える
      • 1歳つがいの数と3歳以上のつがいの数は同じなので、半分になるときは3歳以上を0にして2歳を半分にすると良い
      • しかしその半分があるせいで、単に1000000009でmodとると正しくないですね
        • そこを上手くやってくれ、という問題か
      • 1000000009*2でmodとっても…だめか
      • 1000000009進数を作って、上の桁は2^50まで保持するようにしたらどうだろう
      • 書いている途中に時間切れ
    • 900
      • とりあえず読んでみたがさっぱりわからん
  • Challenge
    • 600を終了直前に出している青い人がいたが案の定すぐ落とされた
    • 300をざっと見てみるが量が多いのでなかなか読めない
    • シミュレーションの初期状態を生成するのに、17!回のループが発生しているように見えるコードがある。TLEするのでは
    • しかし順位が300早解き競争になっていて、-25になったら痛いのでやめておいた
      • そのコードはSystemTestでは落ちていたがTLEではなかった。投げなくて良かった
  • System Test
    • 300通った

結果

  • スコア:217.24 + 0.00 + 0.00 + (50*0-25*0) = 217.24
  • 順位:68位/544人
  • レート:1961→2038

2000! この日記を始めたときに書いていた目標に到達できました。

次がTCO Round3だからキープは厳しいかもしれないががんばろう。

 |