Hatena::Grouptopcoder

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

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

 | 

2010-12-10

[]SRM 490 02:33 はてなブックマーク - SRM 490 - TopCoderの学習のお時間

2010-12-08 25:00-(JST

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

猛省すべき


Levelタイトル試合中あとでひとこと
250StarportAC 6min-焦ってしまった
550QuickT9WA 45min惜しかった
1000InfiniteLabOpened-解けそうな気はするが

  • Coding
    • 250
      • NとMが互いに素だったら0〜N-1が全部1回ずつ出現する
        • 証明:背理法。
        • A*M ≡ B*M (mod N) となるA,B(1<=A<B<N)が存在したとすると
        • (B-A)M = KN (K:1以上の自然数) と書けるはずで、MとNは互いに素なのでB-AはNの倍数
        • しかし 1<=A<B<N から B-A < N なので矛盾
      • NとMに共通因数がある場合は、系全体をgcdで割ってからその結果をgcd倍すればよい
      • これは早解き競争だなあ、と思って焦って細かいミスをいろいろしてしまった。もっと早く提出できるはず
    • 550
      • ややこしそう…まあ頑張って実装してDPだなー
      • 引数の仕様を読み違えたり、Object.equals()のオーバーライドで引数をObject型にしていなくてオーバーライドになっておらずはまったりしていたが、サンプル合ったので提出
      • だが2カ所ミスがあった
      • 整数オーバーフロー
        • 最小値を求める問題だからDPテーブルをInteger.MAX_VALUEで初期化していたのだけど、計算の途中で加算があるのでオーバーフローして負の最大値付近の値になっていた
      • いい加減なハッシュの実装
        • 同じキーストロークで入力できる語の集合をグルーピングするためにHashMapを使っていた。が、
        • キーのハッシュ関数の実装がいい加減で衝突が簡単にあり得るものだった
        • equals()の実装もちゃんとやっておらずハッシュ値が一致したら同一と見なしていたので、ハッシュが衝突したら死亡
    • 1000
      • 読んだだけ
      • 1枠分の一番上の列の各マスから一番下の列各マスへ行く最短距離を求めて行列べき乗?
      • あと始点と終点が近くて直接行ける場合にコーナーケースがありそう
  • Challenge
    • 250が皆ちゃんとした解答
    • (N/d-1) を N/(d-1) に誤読してチャレンジミス。酷い
      • 250が易しめで550難しめだから550落ちると-25がとても痛い…
      • 最近レートが高位安定してきた一番の理由は、とにかく失敗チャレンジしないようにしたことだと思っていたのだけど、ここでこのミスは駄目だ
  • System Test
    • 案の定550が落ちて絶望

結果

  • スコア:239.36 + 0.00 + 0.00 + (50*0-25*1) = 214.36
  • 順位:168位/679人
  • レート:2344 -> 2311

意外とレート落ちてない。250が数学ゲーで一瞬で解ける人がそこまで多くなかったおかげか

 |