Hatena::Grouptopcoder

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

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

 | 

2010-06-27

[]TCO10 Algo Round2 23:13 はてなブックマーク - TCO10 Algo Round2 - TopCoderの学習のお時間

2010-06-26 25:00-(JST

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

850人→350人。ここを通過するとTシャツがもらえる


Levelタイトル試合中あとでひとこと
250SnowPlowAC 14min-気づけば非常に単純
500RepresentableNumbersAC 18min-計算量的な工夫なしで通るとは思わなかった
1000BreakingChocolateOpened--
  • Coding
    • 250
      • 問題文に初めて見る単語がある。適当に推測
      • これ難しいな…。ダイクストラとか典型アルゴリズムが適用できないか考えたけど見えない
      • としてる間にどんどん提出されている
      • 250だからそんなに難しいはずないし、連結してれば常に一筆書きできちゃうのではないか?
      • 証明してないけどとりあえずそれで書いてみた
      • サンプル通らない。エッジがひとつもない頂点というのもあり得るのか
      • 修正して提出
      • あとで考えたこと:一筆書き可能なグラフの任意の位置に一組のエッジを付け足しても、そこに行って帰ってくるだけの経路を付け足せて、一筆書き可能なまま
    • 500
      • とりあえず、representableになるのは偶数だけ
      • ある数がrepresentableかは、下の桁から順に見ていって、
        • 偶数で0以外だったら繰り下がりがあるなし両方あり得る
        • 0だったら常に繰り下がり
        • 奇数だったら残りが全部奇数かどうか
        • などをちまちま実装したら判定できる
      • で、これを順に調べていったらいいだけか…? 計算量どうなんだろう。最悪ケースがわからない
      • 最大値である1億がrepresentableだから、どんなに最悪でもループは5000万回ではある
      • とりあえず提出
      • ローカルで100刻みで全部調べてみた→最悪でも100msだ。OK
    • 1000
      • 1000にしてはやさしそうに見える
      • しかし20分そこらで解けるとは思えないので眺めただけにしておいて500のテストをやる
  • Challenge
    • 500は複雑なコードがいっぱいあって落ちそうだけどテストケースが作れない
    • 何もやらず
  • System Test
    • 250、500両方通った

結果

  • スコア:203.98 + 366.81 + 0.00 + (50*0-25*0) = 570.79
  • 順位:112位/774人
  • レート:1843→1961

自己最高レート更新! しかし次回がTCO Round3なので一気に2000到達は辛そう

 |