Hatena::Grouptopcoder

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

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

 | 

2009-09-24

[][]SRM449 00:09 はてなブックマーク - SRM449 - TopCoderの学習のお時間

2009-09-24 00:00-(JST

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

このmedium難傾向はいつまで続くのか


Levelタイトル試合中あとで感想
DIV1 250MaxTriangleAC 35min-整数+平面幾何。
全部調べればよくて計算量もまず大丈夫なんだけど、どのくらいのオーダーで抑えられるか証明できないので
意地になって華麗な解法を探しに行ってしまった。しかしそんなものありません
問題読んだ瞬間単純なコードを書き始めたら200点は超えると思うけどそれだと面白くないからなぁ…うぅむ
DIV1 550HexagonalBattlefieldOpened-DP?
マスの数は最大でも200くらいだから適当に枝刈りしつつ探索すればいける…
わけないよね550だもんねmod付きだもんねなどと思って問題文読んだだけで放置
DIV1 950StairsColoringOpened-面白そうだったのでずっとこれを考えてた。
i+1段の数をi段の場合から求める漸化式は立ったがそれでまともに計算するとO(10億)で無理。
logに落とさないと…と思ってi段をi/2段から作れないか考えてたができるわけないですね

  • Challenge
    • 550と950を提出している人のコードはなんかマジックナンバーが入ってて意味不明
    • 250は全員同じアルゴリズムにしか見えない
    • 何もせず
    • システムテストで250落とした人がけっこう居たけどこれをどうやって解読すればいいのか謎
  • スコア:129.82 + 0 + 0 + (50*0-25*0) = 129.82
  • 順位:412位/792人
  • レート:1630→1625

足踏み中。

[]今週のPKU 00:49 はてなブックマーク - 今週のPKU - TopCoderの学習のお時間

連休中にけっこうやったのでメモ。

基本的に正解者数が多い問題からやってるのでそんな難しいのは入ってません。

  • 1035
    • やるだけ
  • 1042
    • 経路を覚えつつDP
  • 1094
    • サイズが小さいので、全部の文字対について順序関係を持っておけばよい
  • 1118
    • O(N^2)で全部調べるだけ。同じ位置に複数の点がある場合に注意
  • 1151
    • 座標圧縮の練習問題
  • 1152
    • やるだけ。なんでこんなに正答率低いの…?
  • 1159
    • DP。2つ以上前の状態は不要なので捨てることによって空間計算量を抑える
  • 1166
    • 4^9の全通り調べる
  • 1200
    • BitSet.cardinality()
  • 1222
    • 一番上の行を2^6通り全部試す
  • 1226
    • やるだけ。入力サイズ1の場合に引っかけられた
  • 1230
    • greedy。入力形式にはめられてひたすらWAってた
  • 1251
    • もろに最小全域木
  • 1273
    • もろにMaxFlow
  • 1274
    • もろに2部グラフの最大マッチング
  • 1316
    • まさにやるだけ
  • 1458
    • DP
  • 1459
    • multi-source、multi-sinkなMaxFlowの練習問題
  • 3368
    • segment-tree
    • Javaではやたら遅くてTLEしかしなかった。C++では入力をcinにするとギリギリ、scanfを使うと余裕
 |