SRM500

記念&追悼SRMでした。

• -

250. MafiaGame

問題：N人がいて互いに投票しあう。まず投票する人を決めているM人が投票をし、次に残りの人が得票数が最も少ない人から1人をランダムに選び投票する。最多票が同率のときは残り1人になるまで決選投票を行うとき、最後の1人になる確率が最も高い人の確率は？

• 問題文長いなぁ…。
• 問題の意味を理解するも解法がなかなか見えない。

• 冷静に考えたらM人の投票で2票以上入る人しか最初の投票で残らなくね？
  • M人投票した時点で0票の人が多くてもN-M人しかいない。
  • 残り票はこの人達で全部消費される。
  • M人の投票で2票以上がいなければ全員に1票になって無限ループ
• しかもM人の投票で最多票じゃなければ最初の投票で残らない。
  • 他の票が0票の人たちで全部消費されるので、追いつくことはありえない。
• 2回目に残る人に差異はないし、決着がつくなら(1.0/2回目の残り人数)が答えっぽい。

• 決着がつくかの判定は…。
  • 投票に自由度がある人の人数が残り人数で割りきれたら無限ループに入る。
  • そうでなければ、割った余りの人数が次の投票に残る。
  • ので、無限ループをチェックしつつ残り1人になるまでシミュレーションする。
• という感じで書いてみたらサンプル通ったので、提出。時間かかったな…。

500. FractalPicture

問題：与えられるフラクタル図形の500番目の図形のうち、(x1,y1)、(x2,y2)を頂点にもつ長方形に入る線分の長さの総和を求める。

• また問題文なげー。しかも実装めんどくさそう…。
• …再帰で書いたら楽そうだけど、500回分重ねるのは誤差が怖い。

• とりあえず、再帰しながら1x1のブロック単位でチェックする方針に。
• まず、finalの線分について長さ1単位で長方形内にあるかチェック。
  • 間に合うし、まぁいいかという事で。
• nonfinalの線分3本について再帰的に処理。

• 深さ5のところで関数に渡される線分の長さが1になる。
• ここで与えられた線分の右側・左側に生成される全ての線分は1x1のブロックに入る。
• この長さの和って厳密に計算できたりは…。
  • 与えられた線分の長さは1
  • 次は長さ1/3の線分が2本生成される
  • 次は長さ1/9の線分が6本生成される
  • 次は長さ1/27の線分が18本生成される
  • n回目で、長さ3^-nの線分が2*3^^n-1本生成されて、長さの総和は2/3…?
• 長さ1の時点で5番目の図形なので、あと495回展開される。
  • よって展開される線分の長さの総和は495*2/3になり、片側で495/3 = 165。
• なので、深さ5のところでは線分の左右のブロックが長方形内にあれば165を足す。

• ってやったらサンプルが通り、最大ケースも正しそうだったので提出。

• -

結果：AC / AC / -- ，412.50pt, 21位
レーティング：2193 -> 2308

何とかどちらも通り、ついに念願のレッドコーダーになることができました。
部屋の500は、俺の以外が誤差で落ちてたので、495/3について説明を求められたりも。
訳の分からない英語を書いてみましたが、ギリギリ通じたっぽいので安心もしました。

また、部屋1位だったので私の分の賞金はrem氏の遺族に寄付となりました。
ご冥福をお祈りします。