cafelier@SRM

SRM470

SRM | 16:38 |

SRM470 の成績・ソース (要ログイン) : AC/AC/- : ハチワンダイバー脳

• 書くの忘れてたので思い出しながら簡単にまとめ

500開く

• 『長方形の上辺にN個の点と下辺にN個の点が並んでます。1対1でランダムに結んだときに、交叉する線ペアの個数の期待値は？ただし、K本は初期状態から固定で結ばれてます』
  • N≦10000
  • K≦50

• 別々に考えて
  • 最初のK本どうしの交叉の数
  • 最初のK本 vs 残りN-K本の交叉の数の期待値
  • 残りN-K本どうしの交叉の数の期待値
• を求めて足し算でいいはず。
• 一個目は簡単。K≦50なので数えるだけ。
• 二個目は、K本それぞれについて、残りとの交叉の期待値を求めて和でいいかな
  • a番目とc番目を結んでるとすると
    • (a-1)・(N-a)
    • (c-1)個・(N-c)
  • みたいな状況なので…左上のa-1個に対して右下のN-c個から割り当てるパターン数みたいなのを数えて掛け算して和をとって色々
  • 式をいろいろいじってると綺麗なのが出た。これだ。
• 三個目は…
• わからん…
• これ、独立に数えていいのかなあ。
• 左からi番目の上の点から始まる線とj番目の上の点から始まる線が交叉する期待値、の総和
• これなら簡単なんだけど
• わからん…
• 確率わからん…

• と、独立かどうか結局全然分からない。
• 全然わからないけど
• 直前までハチワンダイバー全巻読み返していた私の思考パターンに隙はなかった

「今のぼくには何も読めない。」

「だから…」

「あなたに読んでもらう」

• 今のぼくには確率がわからない…だから、サンプルデータに読んでもらう！

（詰みがあるなら銀を取る。詰みがないなら、銀は取れない。さあ、どっちだ？！）

• 間違っているなら、Wrong Answer になる。間違っていないなら、WAは出せない。さあ、どっちだ？！

• ということで独立と仮定して書いてみたらサンプルが通ったので出しちゃいました。

250開く

• 『横に並んだ部屋を色の付いた扉が沢山しきっている。色は16色ある。0番目の部屋に自分、N-1番目の部屋に相手がいて、T番目の部屋に宝物がある。交互に（まだコールされてない）色をコールしたら、その色の扉が全部開く。両者最善を尽くしたとき、どっちが勝って何手でゲームが終わる？』
  • 最善を尽くす＝必勝手があるならそれを。できるだけ手順が短くなるように。
  • 負けしかないならできるだけ手数を引き延ばすように

• 色は16色しかないので、それぞれ開いてるか開いてないかで、状態空間は 2^16 しかない。

あと１分。

「長いね。１分もあればいい。」

「ここから」

「あらゆる変化を」

「一 万 手 読 ん で や る ！」

大 ダ イ ブ ！！！！！！

• 制限時間2秒もあれば、あらゆる変化を65536手読んでやる！
• ということでゲーム木を全探索してスコア計算するルーチン書いた。
• 「最善を尽くす」の定義が把握できてなかったので手間取ったけど、
• 結局これ普通にゲーム木探索書いたら一番書きやすい定義ということか…なるほど

• できた
• submit

撃墜タイム

• 1000は見ている時間がなかった。
• 250、宝部屋の左と右にある扉の集合を数えて簡単な足し算と引き算しているだけで解いている人が多数…
• ぬぬー
• ダイブ！！！とかやっていたらゲーム木探索する解しか思いつかなくなってしまっていた！

まとめ

• ハチワンダイバー面白いのでアルゴリズマーの皆様ぜひ読みましょう。