{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n\t\t\t\n\t\t\t\u003cfont color\u003d\"FF0000\"\u003eこの問題は正しく採点されていないという報告を受けています。\u003c/font\u003e\r\n\u003cp\u003eところで,G○○gle Code Jam の地区大会で右の席に座っていた男の\r\nID は rng_58 と言うらしい.\r\n東京大学時代の記憶に,似たような ID の仲間が居た覚えがあるが,僕の仲間は一人残さず美少女だったはずだ.\r\n彼女はいわゆる無表情不思議系キャラだったような気がする.\u003c/p\u003e\r\n\u003cp\u003eということは,彼は知らない男だ.rng とは何の略だろう.\r\nおそらく Random Number Generator に違いない.\r\n乱択アルゴリズムを得意とするのだろう.\u003c/p\u003e\r\n\u003cp\u003eところで,乱数を用いた平衡二分探索木である Treap は,\r\n2011 年頃のプログラミングコンテストではしばしば用いられていたようだが,\r\n20XX 年の今では,あまり使用されていない.\u003c/p\u003e\r\n\u003cp\u003e当時 Treap は実装が平易であるという理由により Splay 木や Scapegoat 木と並んでよく使われていた.\r\n20XX 年の今,命をかけたプログラミングコンテストが日常的に行われるこの世界では,\r\n実装が多少平易になるというような甘い根拠での選択は到底考えられない.\r\n皆,少しでもプログラムが高速になるよう考えているし,\r\n世界大会出場者ともなれば,Left-leaning 赤黒木程度なら十数秒で記述できるのが当然だ.\u003c/p\u003e\r\n\u003cp\u003e例えば,Treap が赤黒木よりも遅くなってしまうのは,\r\n高さの定数倍が効いてくるからであると言われている.\r\nここは,落ち着いてそれを数値的に考察することにより,精神の安定を取り戻そう.\u003c/p\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id1\"\u003e\r\n\u003ch2\u003e問題\u003c/h2\u003e\r\n\u003cp\u003eキーを実数とする Treap に \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e 個のランダムな要素を挿入した際に,\r\n高さが \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eh\u003c/i\u003e\u003c/span\u003e (\u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eh\u003c/i\u003e\u0026nbsp;\u003d\u0026nbsp;0,\u0026nbsp;1,\u0026nbsp;…,\u0026nbsp;\u003ci\u003eN\u003c/i\u003e\u0026nbsp;-\u0026nbsp;1\u003c/span\u003e) となる確率を求めよ.\r\n以下,より詳しく説明する.\u003c/p\u003e\r\n\u003cp\u003eTreap とは乱数を用いた平衡二分探索木である.\r\n各ノードは,キーの他に,優先度という値を持つ.\r\nここでは,キーと優先度は \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e0\u003c/span\u003e から \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e1\u003c/span\u003e までの実数値とする.\r\nTreap では,以下の 2 つの条件が常に保たれる.\u003c/p\u003e\r\n\u003col class\u003d\"arabic simple\"\u003e\r\n\u003cli\u003eキーに関する条件\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\u003cblockquote\u003e\r\n\u003cul class\u003d\"simple\"\u003e\r\n\u003cli\u003e各ノードに関して,左の子以下のノードは自分より小さなキーを持つ\u003c/li\u003e\r\n\u003cli\u003e各ノードに関して,右の子以下のノードは自分より大きなキーを持つ\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/blockquote\u003e\r\n\u003col class\u003d\"arabic simple\" start\u003d\"2\"\u003e\r\n\u003cli\u003e優先度に関する条件\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\u003cblockquote\u003e\r\n\u003cul class\u003d\"simple\"\u003e\r\n\u003cli\u003e各ノードに関して,子のノードは自分より小さな優先度を持つ\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/blockquote\u003e\r\n\u003cp\u003e下図は,Treap の例である.\r\n各ノードの,上部にキーが,下部に優先度が書かれている.\u003c/p\u003e\r\n\u003cdiv class\u003d\"figure align-center\"\u003e\r\n\u003cimg alt\u003d\"//img.atcoder.jp/utpc2011/treap_fig1.png\" src\u003d\"CDN_BASE_URL/b5878c57660f30733b1aec0bcb5ffbbe?v\u003d1715274183\"\u003e\r\n\u003cp class\u003d\"caption\"\u003e7 つのノードからなる Treap の例.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cp\u003e挿入の操作は,以下のように行われる.\r\n挿入するキー を \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e とおく.\u003c/p\u003e\r\n\u003col class\u003d\"arabic simple\"\u003e\r\n\u003cli\u003e挿入する新しいノードの優先度 \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ep\u003c/i\u003e\u003c/span\u003e を \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e0\u003c/span\u003e から \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e1\u003c/span\u003e までの一様分布よりランダムに決定する.\u003c/li\u003e\r\n\u003cli\u003e通常の二分探索木と同様に,まずは優先度を無視し新しいノードを挿入する.\u003c/li\u003e\r\n\u003cli\u003e優先度の条件を満たすように,新しいノードを上に持ち上げるような回転操作を必要なだけ繰り返す.\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\u003cp\u003e木の回転操作に関しては,補足の節に詳しく記述したので,参考にせよ.\u003c/p\u003e\r\n\u003cp\u003e下図は,先ほどの例にキーとして 0.5,優先度として 0.7 を持つ頂点を挿入した過程の例である.\u003c/p\u003e\r\n\u003cdiv class\u003d\"figure align-center\"\u003e\r\n\u003cimg alt\u003d\"//img.atcoder.jp/utpc2011/treap_fig2.png\" src\u003d\"CDN_BASE_URL/8328ebd23a33645197baaf3ea4b85632?v\u003d1715274183\"\u003e\r\n\u003cp class\u003d\"caption\"\u003eまずは優先度が無視され,ノードが挿入される.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"figure align-center\"\u003e\r\n\u003cimg alt\u003d\"//img.atcoder.jp/utpc2011/treap_fig3.png\" src\u003d\"CDN_BASE_URL/5389673c91407806da2b085f7a3eb1df?v\u003d1715274183\"\u003e\r\n\u003cp class\u003d\"caption\"\u003e回転を行い新しいノードが上へ行く.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"figure align-center\"\u003e\r\n\u003cimg alt\u003d\"//img.atcoder.jp/utpc2011/treap_fig4.png\" src\u003d\"CDN_BASE_URL/7816f07e2ce81dbf5a41b04d1a995695?v\u003d1715274183\"\u003e\r\n\u003cp class\u003d\"caption\"\u003eさらに回転を行うと,優先度の条件が満たされるので,挿入は終了する.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cp\u003e空の Treap に \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e 個のキーを,\r\nやはり \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e0\u003c/span\u003e から \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e1\u003c/span\u003e までの一様分布よりランダムに選び挿入してゆくとする.\r\n最終的に高さが \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eh\u003c/i\u003e\u003c/span\u003e となる確率を,\r\n各 \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eh\u003c/i\u003e\u0026nbsp;\u003d\u0026nbsp;0,\u0026nbsp;1,\u0026nbsp;…,\u0026nbsp;\u003ci\u003eN\u003c/i\u003e\u0026nbsp;-\u0026nbsp;1\u003c/span\u003e について求めよ.\r\nなお,実数は十分な精度を持って扱われるとし,\r\n例えば 2 つのノードの優先度が等しくなる確率は 0 としてよい.\r\nまた,高さとは,根のノードから各ノードに至るために通らなければならない辺の本数の最大値である.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id2\"\u003e\r\n\u003ch2\u003e入力\u003c/h2\u003e\r\n\u003cp\u003e1 つの整数 \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e が書かれている.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id3\"\u003e\r\n\u003ch2\u003e出力\u003c/h2\u003e\r\n\u003cp\u003e出力は \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e 行から成る.\r\n\u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e 行目に高さが \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ei\u003c/i\u003e\u0026nbsp;-\u0026nbsp;1\u003c/span\u003e となる確率を出力せよ.\r\n値は小数点以下何桁表示しても構わない.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id4\"\u003e\r\n\u003ch2\u003e制約\u003c/h2\u003e\r\n\u003cul class\u003d\"simple\"\u003e\r\n\u003cli\u003e\u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e1\u0026nbsp;≤\u0026nbsp;\u003ci\u003eN\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;3\u0026nbsp;×\u0026nbsp;10\u003csup\u003e4\u003c/sup\u003e\u003c/span\u003e\u003c/li\u003e\r\n\u003cli\u003e出力する値は \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e10\u003csup\u003e\u0026nbsp;-\u0026nbsp;5\u003c/sup\u003e\u003c/span\u003e 以下の誤差を含んでいても構わない.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id5\"\u003e\r\n\u003ch2\u003e入出力例\u003c/h2\u003e\r\n\u003cp\u003e入力例 1:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\n1\r\n\u003c/pre\u003e\r\n\u003cp\u003e入力例 1 に対する出力例:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\n1.0\r\n\u003c/pre\u003e\r\n\u003cp\u003e入力例 2:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\n2\r\n\u003c/pre\u003e\r\n\u003cp\u003e入力例 2 に対する出力例:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\n0.0000000000\r\n1.0000000000\r\n\u003c/pre\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id6\"\u003e\r\n\u003ch2\u003e補足\u003c/h2\u003e\r\n\u003cp\u003e木の回転操作には,右回転と左回転がある.\r\n右回転とは,以下の 2 つの図の 1 つめの状態を 2 つめの状態にする操作であり,\r\n左回転とは,以下の 2 つの図の 2 つめの状態を 1 つめの状態にする操作である.\u003c/p\u003e\r\n\u003cdiv class\u003d\"figure align-center\"\u003e\r\n\u003cimg alt\u003d\"//img.atcoder.jp/utpc2011/treap_fig_rot1.png\" src\u003d\"CDN_BASE_URL/af1801d04c477a7c78b7b3ac4337f7f8?v\u003d1715274183\"\u003e\r\n\u003cp class\u003d\"caption\"\u003e右回転をする前,または左回転をした後\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"figure align-center\"\u003e\r\n\u003cimg alt\u003d\"//img.atcoder.jp/utpc2011/treap_fig_rot2.png\" src\u003d\"CDN_BASE_URL/3648e52721b2bb3390076d5eda01d1af?v\u003d1715274183\"\u003e\r\n\u003cp class\u003d\"caption\"\u003e右回転をした後,または左回転をする前\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cp\u003eTreap においては,持ち上げたいノードがその親ノードの左の子であった場合,\r\n持ち上げたいノードを上図の P とするような右回転を適用し,\r\n持ち上げたいノードがその親ノードの右の子であった場合,\r\n持ち上げたいノードを上図の Q とするような左回転を適用する.\u003c/p\u003e\r\n\u003cp\u003e木の回転操作について,より詳しくは,例えば以下を参照せよ.\u003c/p\u003e\r\n\u003cul class\u003d\"simple\"\u003e\r\n\u003cli\u003e\u003ca class\u003d\"reference external\" href\u003d\"http://ja.wikipedia.org/wiki/%E6%9C%A8%E3%81%AE%E5%9B%9E%E8%BB%A2\"\u003ehttp://ja.wikipedia.org/wiki/%E6%9C%A8%E3%81%AE%E5%9B%9E%E8%BB%A2\u003c/a\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eTreap について,より詳しくは,例えば以下を参照せよ.\u003c/p\u003e\r\n\u003cul class\u003d\"simple\"\u003e\r\n\u003cli\u003e\u003ca class\u003d\"reference external\" href\u003d\"http://en.wikipedia.org/wiki/Treap\"\u003ehttp://en.wikipedia.org/wiki/Treap\u003c/a\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003ca class\u003d\"reference external\" href\u003d\"http://www.prefield.com/algorithm/container/treap.html\"\u003ehttp://www.prefield.com/algorithm/container/treap.html\u003c/a\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/div\u003e\r\n"}}]}