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到達は辛そう

[]TCO10 Algo Round1 22:48 はてなブックマーク - TCO10 Algo Round1 - TopCoderの学習のお時間

2010-06-19 25:00-(JST

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

2000人くらい→850人。ICFPCの最中。


Levelタイトル試合中あとでひとこと
250EqualizeStringsAC 5min-コーナーケースがありそうでなかった
500TwoRegistersCompiled-探索での計算量見積もりが弱い
1000VacationToursUnOpened-部屋内で誰も提出してなかったので開かず
  • Coding
    • 250
      • 文字ごとに独立にやればいいですよね
      • どちらか小さい方に合わせるのに必要なステップ数と、両方とも'a'にするために必要なステップ数を出して、小さい方で。同じなら'a'
      • サンプル通った、提出
    • 500
      • うわ、lexicographical orderきちゃった(なぜかこれが出てくるのは苦手)
      • とりあえずBFS書いてみた→MLE。まあそりゃそうだ
      • 最大10^6ということは、1回の操作で値が大体2倍になるからlog(10^6)≒20回くらいの操作で答えが出るのではないか?
        • (※間違い。フィボナッチ数なのでせいぜい黄金比倍にしかならない)
      • ならば2^20通り全探索すればいい
      • 書いた。TLE。ううむ
      • あ、これ逆から考えたら状態分岐しない…
      • 書いた
      • バグった
      • 終了
  • Challenge
    • Division Summary見ると通過ライン上あたり
    • きっと他の人の500はたくさん落ちるだろから、チャレンジミスで-25しなければ通過できるだろう。おとなしくしておこう
  • System Test
    • 250通った
    • あとは順位が上がっていくのを見てた。最終的に200くらい上がった

結果

  • スコア:241.85 + 0.00 + 0.00 + (50*0-25*0) = 241.85
  • 順位:649位/1439人
  • レート:1875→1843

250でスムーズに提出できて助かった

 |