Hatena::Grouptopcoder

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

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

 | 

2010-02-08

[][]SRM460 01:54 はてなブックマーク - SRM460 - TopCoderの学習のお時間

2010-02-06 26:00-(JST

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


Levelタイトル試合中あとでひとこと
DIV1 250TheQuestionsAndAnswersDivOneWA 35min場合の数は得意な方のはずなのに大混乱
DIV1 500TheFansAndMeetingsDivOneWA 37minintオーバーフローと定数倍最適化
DIV1 1000TheCitiesAndRoadsDivOneUnOpened- 
  • Coding
    • 250
      • とりあえず全部調べたら9^9だけど計算量が不安
      • 場合の数で出せそうなので考える
      • が焦ってしまってグダグダ。間違った回答がサンプル通っちゃってそのまま提出してしまった
    • 500
      • ん、DP…でいいのか? 計算量40*40*40*1600=約1億になるけど…
      • ええいもう時間がない書いてしまえ
      • なんか係数があってないみたいでサンプルの答えが合わない
      • 250から2項係数のコードを持ってきて割り算してみたら合った。ここで残り20秒、大きいケースでTLEしそうだけどもういいや提出
  • Challenge
    • 500落とされた。これは予想通り
    • 250も落とされてしまった
    • 250を探索しているコードでTLEが狙えたかもしれないが-25が怖すぎる
  • System Test
    • みてるだけ
  • スコア:0.00 + 0.00 + 0.00 + (50*0-25*0) = 0.0
  • 順位:427位/651人
  • レート:1834→1705

ベースラインに押し戻され。


250は、落ち着いている状況ではあり得ないような勘違いでした。SRMは3問(実質2問)しかないからやけに緊張してしまう。

500は、250から持ってきた2項係数を計算するコードがint型のままだったので、40C20とかきたらオーバーフローしちゃいます。これは残り20秒じゃしょうがない。

あとやっぱり定数倍最適化しないとTLEしてました。

[][]SRM459 01:35 はてなブックマーク - SRM459 - TopCoderの学習のお時間

2010-01-19 25:00-(JST

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

サンプルはよく読みましょう


Levelタイトル試合中あとでひとこと
DIV1 250InequalitiesAC 10min-やるだけ、ほどよい作業量
DIV1 500NumberPyramidsCompiled 66minDPなのはすぐ分かったがあと一歩が
DIV1 1000TheContestUnOpened-誰も正解してない
  • Coding
    • 250
      • 最高1000までということは、全部調べりゃいい
      • 整数しか考えないものと思い込んで、-1〜1001まで1刻みで調べていてサンプルが通らず焦る
      • サンプルをよく読んで実数の範囲と理解
      • というわけで0.5刻みで調べるとサンプル通ったので提出
    • 500
      • 高さ>20 ならばすぐ return 0; で良いのと、一番下の桁に着目して2項係数を重みとするナップザック的DPを解けばよいのはすぐわかった
      • 一桁の数しか入れられないものと思い込んで愚直にDP書くとサンプルが合わない
      • サンプルをよく読んで、10以上も入れて良いことを把握
      • とすると計算量がbaseLength*top*topになってダメだ
      • ずっと考えたが効率の良い方法がわからず
      • 手持ちぶさたになったので、端からではなく係数の大きい真ん中から調べていくコードを書いて、「おお確かに数倍は速くなる」とかやってた。どうしようもない。
      • 後でうまく書けている人のコードを見るとシンプルで感激
  • Challenge
    • 250でどう見ても間違ったことやってる人がいたのだけどチャレンジしてみたら失敗
    • よーく読むと、どうして間違ってるのにたまたま通っちゃったのかわかった!
    • と思った瞬間他の人に落とされた…
  • System Test
    • 250は通った
  • スコア:219.51 + 0.00 + 0.00 + (50*0-25*1) = 194.51
  • 順位:364位/653人
  • レート:1887→1834

最低でも半分より上には入らないと厳しいね。

 |