Hatena::Grouptopcoder

ir5は引退した

 | 

2010-07-06

SRM475

02:42

うっさうさな回でした.

DivLevelProblemNameStatus
1300RabbitSteppingPassed System Test
1600RabbitIncreasingOpened
1900見てないUnopened

300

  • 問題文にうさぎが.うさぎがゲームしてるなんてかわいい… というのはさておき.
  • 問題文長い.読むのに時間掛かる.
  • 何かゲームをして残ってる人数の期待値とかを求めるらしい.へぇー.
  • どうやるの… ちゃんと考えれば分かるのかもしれないが,全然見当が付かない.
    • Nが非常に小さい.(N<=17) 全部調べるのか?
    • 組み合わせ係数C(17,8)はとても小さいので全部愚直に調べても大丈夫そう.
  • 実装ゲーか… 書く.
    • ビット使って高速化しようかなーとか悩んでいると結構時間が経っていた.結局vectorとか使って愚直なシミュレートをした.
  • 書けた.ここまで20分くらい.テスト.通らない.
    • というか途中で無限ループしてる.
    • ゲームの終了条件を間違えていた.残りのマスが<=2となるところで終了なのに,残り匹数が>=2で終了としていた.修正.
    • まだおかしい.
    • 期待値じゃなくて,1匹以上残る確率を求めていた.修正.
    • まだ通らない.無限ループしてるところもある.
    • 組み合わせ係数のループが普通のループになってた.これはだめだろう… ビットの個数を保持して次に大きい数を返す関数を持ってきて修正.
    • うーん… assertしてみよう.
    • どうも終了時に3匹以上残っている場合があるらしい.んなアホな….
    • if ()... if ()... if ()... となっているところあるけど,これ正しくはif ()... else if ()... else if ()... では?
    • 直した.サンプル通った.
    • → 提出.ここまで36分くらい.遅いよ….

600

  • ここまででルーム内の真ん中くらいの順位.今回はそこまでレベルの高いルームではないから実際はもうちょっと下の方な気がする.頑張らないと.
  • 問題開いた時点では誰も提出してない.難しいの?
  • またしてもうさぎ.うさぎがいっぱい増えていく問題.うっさうさ.
    • うさぎが基本的にフィボナッチみたいな感じで増えるのだけど,ときたま半分のうさぎが外国へ旅立ってしまうらしい.どんな問題設定なんだ.
    • N<=10000000.定数オーダーじゃないと駄目かなぁと思ったけど,定数倍の速さに気をつければO(N)でもいい.
  • どうすんのこれ.
  • 生まれて0年目のウサギの数をa0,1年目のウサギの数をa1,2年目以降のウサギの数をa2とすると漸化式が容易に経つ.あれ,これそのまんまなんじゃ?
    • 書く.

  • 詰まる.MODしてるのに,全体の半分の匹数ってどうやって求めるのよ.
  • なんか上手い感じにやればできる気がせんでもないけど分からない.
  • そもそもどれくらい減るんだろう…
  • 色々考えるけど分からない.
  • ルーム見る.誰も提出してない.Division Summaryも見る.30人くらいしか出してない.なんじゃそりゃ.
    • 諦めた.

Intermission

  • 終了間際に600で悪あがきの提出をしている人(青色コーダー)を発見.この人専用に大きめのテストを作る.
  • Twitterでちょっとだけうさうさする.「「

Challenge Phase

  • 開始と同時に何も考えず大きめのテストを投げる.成功.+50
  • 撃墜できる問題があとは300しかない.色々見る.
  • 今回はみんな順位が似たり寄ったりなので割と慎重にやった方がいいだろうなーとか考えつつ開いたりする
  • 全通り列挙するループで, for (int i=0; i<Math.pow(2,N)-1; ++i) .. みたいにしてる人がいる.…なんで1引いてるんだろう.
    • とりあえず "WWW",3とか投げる.成功.+50
  • 他に撃墜できそうな人いるかなぁ… → いない.終了.

System Test

  • 300通った.提出遅かったけどチャレンジが功を成したのか妙に順位高い.
  • なんか運でレート上がった感じがする.

o x x 252.54 41/598 1532->1724

 |