Hatena::Grouptopcoder

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

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

 | 

2010-07-18

[]SRM476 22:58 はてなブックマーク - SRM476 - TopCoderの学習のお時間

2010-07-17 25:00-(JST

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

赤い人が居ない部屋。撃墜のチャンス


Levelタイトル試合中あとでひとこと
250BadgersAC 5min-Easyには程よい問題と思うが550が難しくて早解き競争になったのが残念
550FriendTourOpened-引っかけの1つは気づけたがもう1つを見落とし
1000SpaceshipEvacuationOpened-読み流しでは理解できなかった

  • Coding
    • 250
      • む、ナップザックDP
      • てことはないか。greedyにコストが小さいやつから取っていけばよいね
      • N<=50なので1匹〜N匹まで全部試して大丈夫
      • サンプル通って提出、部屋内9番目
      • この日はSRM以外でまったくタイピングしてなかったので手が遅い
    • 550
      • これってまともにやると巡回セールスマンだから2^36で無理だ
      • constraintsで"36 characters"となってるのに気づく。ということは最高15人しか隣接しない
      • とはいえ、TopCoderでそんなところがポイントになるような引っかけがあるはず無いでしょ
        • (甘い)
      • それに、35人巡らないといけないのならオーダー的にはたぶん変わらない
        • (最初の人の直接の友達しか訪問しないことに気づいていない)
      • 「一筆書き 最短距離」などで検索してみるも意味なし。そりゃそうだ
      • まともな方法で無理ということは、対称性とか何か数学的な性質を使って単純化するのか?
      • わからん
      • 最後には、サンプルの答えを分析して簡単な式で表せないか探るというたいへん不毛なことをやっていた
        • それが可能なのならサンプルはもっと不親切になるはず
    • 1000
      • 部屋内で提出している人がいたのでとりあえず読んでみた
      • 問題文が長くて複雑…流し読みでは全く理解できない
      • そっと閉じた
  • Challenge
    • 全体的に250の早解き競争になったので1つでもチャレンジ成功させたら大勝利
    • 250はサンプルでカバーされていないコーナーケースがいろいろあるので狙えるかも
      • 答えが0
      • 答えがN
      • 入力サイズが1
      • 最大ケース
    • 入力サイズ1を考慮していない人発見! 撃墜成功
    • 他に、2分探索が怪しげな人がいたがちゃんと読むのを後回しにしている間に他の人に撃墜された
  • System Test
    • 250通った
    • 部屋の550と1000は全部落ちてた

結果

  • スコア:240.57 + 0.00 + 0.00 + (50*1-25*0) = 290.57
  • 順位:77位/721人
  • レート:2198→2252

f:id:tomerun:20100718225718p:image

2年前に競技プログラミング始めたときには遙か彼方の存在だったレッドコーダーに、遂になってしまいました…。現実感がない。

今回はMediumが解けずちょっとしょっぱい感じでしたが、リーチ一発で決められてよかった。

まだまだ脳は成長できる余地がありますよ世の20代後半のみなさん!(※僕はもうすぐ27歳です)


さてしかしエンジニアとしては自分には「TopCoderの問題が解ける」以外の取り柄が無くて、とても身に余る称号としか思えないのが心苦しいところ。

その名に恥じないように自分を成長させていくよう、この結果をうまくブースターとして利用できれば。

 |