2010-12-10

■ [SRM]SRM 490 02:33

2010-12-08 25:00-（JST）

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

猛省すべき

Level	タイトル	試合中	あとで	ひとこと
250	Starport	AC 6min	-	焦ってしまった
550	QuickT9	WA 45min	○	惜しかった
1000	InfiniteLab	Opened	-	解けそうな気はするが

• Coding
  • 250
    • NとMが互いに素だったら0〜N-1が全部1回ずつ出現する
      • 証明：背理法。
      • A*M ≡ B*M (mod N) となるA,B(1<=A(B-A)M = KN (K:1以上の自然数) と書けるはずで、MとNは互いに素なのでB-AはNの倍数
      • しかし 1<=A
      • 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が数学ゲーで一瞬で解ける人がそこまで多くなかったおかげか