2010-11-14

■ [SRM]SRM 487 01:37

2010-11-13 26:00-（JST）

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

Level	タイトル	試合中	あとで	ひとこと
250	BunnyComputer	AC 8min	-	もっと速く書きたかった
550	BunnyExam	WA 21min	-	反例の探し方が下手だった
950	BunnySequence	AC 37min	-	950にしては易しめか

• Coding
  • 250
    • 絵があると理解しやすいですね
    • 少し考えるとK+1本のラインに分割して独立に扱えることがわかる
    • DPかとちょっと思ったが、もっと簡単にできる方法を思いついた
    • 偶数個だったら全部使えるし、奇数個だったら偶数番目のものどれか1つが使えないので最小のを捨てる
  • 550
    • 出た期待値の線形性（好物）
    • とりあえず選び方が存在する場合の答えは線形性からm/kで良い。多分に直感的だけど
    • 選び方が存在するかどうかは…
      • k=1,2の場合は簡単
      • 3以上の場合は選べないケースを思いつけなかった
      • 550だからそんな簡単なはずはなかろうが…
    • もし950が自分にも解答可能なレベルだったら、ここであまり粘ると逃してしまう（結果的にこの判断は正解だった）
    • とりあえずkが3以上の場合は常に条件を満たせるとして提出
  • 950
    • お、数論。これはいけるかも
    • 入力が100万なのでDP的にO(N)かデータ構造こねこねしてO(NlogN)か、てとこだろう
    • サンプルにあったm=3,n=4のケースの樹形図を書いて構造を把握
    • 「*」または「-」を、「-」がm個以上連続しないようにn-1個並べる場合の数の問題として構成できた
      • ただし 1->3->2->1 みたいに1に戻るのを禁止するため、先頭だけは「-」はm-2個までしか連続できない
    • ここまではすぐだったのだけど、これをO(N)で求める方法がわからなくて
    • 20分くらいぐちゃぐちゃ考えていたらやっとDPでいける方法が思いつけて
    • 2分前に書き上げられました
    • 他の人の解答を見たらとても短いのでもっとシンプルな考え方があったのだろう
• Challenge
  • 550がすぐさま撃墜されていった。まあ予想通り
  • 550でm=1とかk=1,2の場合をざっと見たが落ちそうなのはなく
  • 250を読んでいく
  • 計算量がO(2^N)でTLEしそうなコードがあった。自分の950が通っている自信がなくて-25すると悲劇なのでじっくり確認していたら他の人に落とされた。仕方ない
• System Test
  • 250も950も通った。初のHard正解

結果

• スコア：231.36 + 0.00 + 474.56 + (50*0-25*0) = 705.92
• 順位：30位/753人
• レート：2266 -> 2344

highest!

でも550でk=3の反例が思いつけなかったのは反省すべき。適当にランダムに並べつつ反例を探していたけれど、問題の制約から論理的に構成していくような考え方をしないと。

■ [SRM]SRM 486 01:37

2010-10-26 25:00-（JST）

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

探索の計算量見積もりが弱いことを再確認した回

Level	タイトル	試合中	あとで	ひとこと
300	OneRegister	AC 39min	-	点数に騙され
450	QuickSort	AC 30min	-	無理やり数学的に
1000	BatmanAndRobin	Opened	-	-

• Coding
  • 300
    • えー幅優先するだけでいいの？
    • なるほど単純にやったら計算量大きいのか。300だしなあ（←勘違い）
    • 逆から考えると計算量押さえられるのかな？
    • 辞書順最小を出すための場合分けの泥沼にはまる
    • 部屋の様子を見ると青い人も続々提出している
    • …
    • 初回に / 使うの以外では1回の操作で2倍か2乗にしかならないから計算量は全く無問題でした
    • 何でこれ300なの…
  • 450
    • 出た期待値の線形性（好物）
    • 反転数でも数えればよいのかと思ったが違った
    • DP的解法も考えたがすっきりまとめられない
    • 結局、次のように考えて期待値の線形性を使って解いた
      • まず、具体的な数値は関係なくて大きさの順番だけが問題なので、入力を0〜N-1のPermutationに置き換える
      • i番目とj番目の大小が反転しているとき、i番目をpivotに選ぶことによって反転が解消する確率を考えると
      • L[j]〜L[i] の (L[i]-L[j]+1) 個の数の中からL[i]が最初にpivotとして使われる場合なので1.0/(L[i]-L[j]+1)
      • これをすべてのi,jの組について足し合わせる
• Challenge
  • 300のコードが多彩でいろいろ見ていたら、yeharaさんのコードが幅優先ではなく深さ優先みたいになっていたので撃墜
• System Test
  • 300も450も通った

結果

• スコア：144.98 + 255.34 + 0.00 + (50*1-25*0) = 450.32
• 順位：160位/721人
• レート：2288 -> 2266

この内容でこれだけ踏みとどまれたのは及第点