{"id":4387,"date":"2023-03-28T22:36:35","date_gmt":"2023-03-28T13:36:35","guid":{"rendered":"https:\/\/k.foolslab.net\/dailyreport\/?p=4387"},"modified":"2023-03-28T22:36:35","modified_gmt":"2023-03-28T13:36:35","slug":"2023-3-28","status":"publish","type":"post","link":"https:\/\/k.foolslab.net\/dailyreport\/2023-3-28\/","title":{"rendered":"2023\/3\/28(\u706b)"},"content":{"rendered":"\n

\u4eca\u9031\u306e\u80ce\u754c\u4e3b\u3092\u8aad\u3093\u3060\u3002\u4e5d\u72fc\u304c\u610f\u5916\u3068\u7269\u7533\u3059\u4f53\u5236\u306b\u306a\u3063\u3066\u3044\u308b\u3002\u3053\u308c\u306f\u30a2\u30d0\u30c9\u30f3\u3067\u306f\u306a\u304f\u672c\u4eba\u306e\u610f\u601d\u3067\u3044\u3044\u3093\u3060\u3088\u306a\uff1f\u4eca\u307e\u3067\u66f2\u304c\u308a\u306a\u308a\u306b\u3082\u7236\u3092\u6155\u3063\u3066\u308b\u611f\u3058\u3060\u3063\u305f\u306e\u3067\u3001\u3069\u3046\u3044\u3046\u611f\u60c5\u3067\u3053\u306e\u767a\u8a00\u3092\u3057\u3066\u3044\u308b\u306e\u304b\u304c\u63b4\u3081\u306a\u3044\u3002\u4e00\u5ea6\u3061\u3083\u3093\u3068\u3076\u3064\u304b\u3063\u3066\u304a\u304d\u305f\u304b\u3063\u305f\u306e\u3060\u308d\u3046\u304b\u3002<\/p>\n\n\n\n

\u4e00\u65b9\u30ec\u30c3\u30af\u30b9\u3001\u524d\u8a71\u6700\u5f8c\u3067\u3059\u3054\u3044\u5263\u5e55\u306b\u306a\u3063\u3066\u3044\u305f\u304c\u3001\u4eca\u56de\u306f\u3044\u3064\u3082\u901a\u308a\u306e\u611f\u3058\u306b\u306a\u3063\u3066\u3044\u308b\u3002\u30a2\u30d0\u30c9\u30f3\u306b\u6c17\u4ed8\u3044\u305f\u4e0a\u3067\u300c\u30b9\u30e0\u30fc\u30ba\u306b\u4e8b\u304c\u904b\u3076\u3088\u3046\u304b\u307e\u3057\u3066\u308b\u300d\u306e\u3060\u308d\u3046\u304b\u3002\u7121\u8cac\u4efb\u98db\u884c\u306e\u6642\u3068\u6bd4\u3079\u3066\u5b50\u80b2\u3066\u8ad6\u8a9e\u308a\u304c\u96d1\u306b\u306a\u3063\u3066\u306a\u3044\u304b\u3002\u30a2\u30c9\u30cb\u30b9\u307f\u305f\u304f\u304b\u304b\u3068\u6d6e\u3044\u3066\u308b\u3057\u3002<\/p>\n\n\n\n

\u4e45\u677e\u306f\u3053\u308c\u5927\u4e08\u592b\u306a\u306e\u304b\uff1f\u6b63\u306e\u5b57\u30ab\u30a6\u30f3\u30c8\u30675\u3064\u4e0d\u8ebe\u306a\u7269\u8a00\u3044\u3057\u305f\u3089\u7206\u767a\u3059\u308b\u3068\u304b\u3060\u3063\u305f\u3089\u5acc\u3060\u305e\u3002<\/p>\n\n\n\n

\u3068\u3053\u308d\u3067\u8aad\u307f\u76f4\u3057\u305f\u3089\u300c\u6708\u66dc\u65e5 2\u300dp26\u306e\u30a4\u30e1\u30fc\u30b8\u3067\u30ec\u30c3\u30af\u30b9\u9774\u8131\u3044\u3069\u308b\u3002\u3053\u308c\u306f\u4e00\u4f53\uff1f<\/p>\n\n\n\n

\u672c\u7b4b\u3068\u306f\u95a2\u4fc2\u306a\u3044\u304c\u3001\u4e45\u677e\u306e\u306e\u308c\u3093\u304c\u300c\u4e45\u300d\u306e\u5b57\u306b\u306a\u3063\u3066\u308b\u306e\u306b\u6c17\u3065\u3044\u3066\u30cb\u30e4\u30cb\u30e4\u3057\u3066\u3044\u308b\u3002<\/p>\n\n\n\n

\n\n\n\n

\u4eca\u65e5\u89e3\u3044\u305f\u7af6\u30d7\u30ed\u306e\u554f\u984c\u3002<\/p>\n\n\n\n

ABC295-E: \u89e3\u8aacAC\u3002<\/p>\n\n\n\n

\u671f\u5f85\u5024\u306e\u5b9a\u7fa9\u304b\u3089\u8003\u3048\u308b\u3068$\\sum_{i=1}^M P(A_K=i)\\times i$\u3060\u304c\u3001$P(A_K=i)$\u3092\u76f4\u63a5\u6c42\u3081\u308b\u306e\u306f\u96e3\u3057\u3044\u3002\u4e00\u65b9$P(A_K\\leq i)$\u306f\u5272\u3068\u6c42\u3081\u3084\u3059\u3044\u3002\u3053\u308c\u3092\u6c42\u3081\u305f\u4e0a\u3067\u306a\u3089$P(A_K=i)=P(A_K\\leq i)-P(A_K<i)$\u3068\u3044\u3046\u5f62\u3067\u6c42\u3081\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3002<\/p>\n\n\n\n

$P(A_K\\leq i)$\u306e\u6761\u4ef6\u3092\u8003\u3048\u308b\u3068\u3001\u3053\u308c\u306f$i$\u4ee5\u4e0b\u306e\u5024\u3092\u6301\u3064\u8981\u7d20\u304c$K$\u500b\u4ee5\u4e0a\u3042\u308b\u3053\u3068\u3068\u540c\u5024\u306b\u306a\u308b\u3002\u5143\u306e\u914d\u5217A(\u304b\u30890\u3092\u53d6\u308a\u9664\u3044\u305f\u3082\u306e)\u306b$i$\u4ee5\u4e0b\u306e\u5024\u304c$K$\u500b\u4ee5\u4e0a\u3042\u308c\u3070\u78ba\u7387\u306f1\u306b\u306a\u308b\u3002\u4e00\u65b9\u3067$i$\u4ee5\u4e0b\u306e\u5024\u30680\u306e\u6570\u3092\u5168\u3066\u5408\u308f\u305b\u3066\u3082$K$\u500b\u306b\u5c4a\u304b\u306a\u3051\u308c\u3070\u78ba\u7387\u306f0\u3002\u554f\u984c\u306f\u305d\u306e\u9593\u3067\u3001\u3053\u308c\u306f\u591a\u5c11\u5730\u9053\u306b\u8a08\u7b97\u3059\u308b\u5fc5\u8981\u304c\u3042\u308b\u30020\u306e\u6570\u3092$z$\u3068\u3057\u3066\u3001$K$\u500b\u306b\u5c4a\u304f\u305f\u3081\u306b\u8ffd\u52a0\u3067\u5fc5\u8981\u306a$i$\u4ee5\u4e0b\u306e\u5024\u306e\u6700\u4f4e\u9650\u306e\u6570\u3092$z_0$\u3068\u3059\u308b\u3068\u4ee5\u4e0b\u306e\u3088\u3046\u306b\u306a\u308b\u3002<\/p>\n\n\n\n

$\\sum_{j=z_0}^z i^j (M-i)^{z-j} \\ _zC_j$<\/p>\n\n\n\n

$z$\u500b\u4e2d$j$\u500b\u304c$i$\u4ee5\u4e0b\u3067$z-j$\u500b\u304c$i$\u3088\u308a\u5927\u304d\u3044\u3068\u3044\u3046\u306e\u3092\u611a\u76f4\u306b\u5f0f\u306b\u3059\u308c\u3070\u3053\u3046\u306a\u308b\u3002\u3053\u308c\u306f\u7279\u306b\u7279\u6b8a\u306a\u5de5\u592b\u3092\u3057\u3066\u9ad8\u901f\u5316\u3057\u306a\u304f\u3068\u3082\u3001\u524d\u8a08\u7b97\u3067\u4e8c\u9805\u4fc2\u6570\u3092$O(1)$\u3067\u3084\u308b\u3044\u3064\u3082\u306e\u3084\u3064\u3068\u4e8c\u5206\u7d2f\u4e57\u3092\u3059\u308c\u3070$O(N\\log N)$\u3067\u6c42\u307e\u308b\u3002\u3053\u308c\u3092$1\\leq i \\leq M$\u306b\u3064\u3044\u3066\u8a08\u7b97\u3059\u308c\u3070$O(MN\\log N)$\u3067\u89e3\u3051\u305f\u3002<\/p>\n\n\n\n

\u306a\u304a\u3001\u3079\u304d\u4e57\u3092\u524d\u8a08\u7b97\u3057\u3066\u304a\u3051\u3070\u8a08\u7b97\u91cf\u3092\u843d\u3068\u305b\u308b\u3002\u524d\u8a08\u7b97\u3059\u308b\u7bc4\u56f2\u306f$i^j(0\\leq i \\leq M, 0\\leq j \\leq N)$\u306a\u306e\u3067\u524d\u8a08\u7b97\u542b\u3081\u3066$O(MN)$\u306b\u306a\u308b\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"

\u4eca\u9031\u306e\u80ce\u754c\u4e3b\u3092\u8aad\u3093\u3060\u3002\u4e5d\u72fc\u304c\u610f\u5916\u3068\u7269\u7533\u3059\u4f53\u5236\u306b\u306a\u3063\u3066\u3044\u308b\u3002\u3053\u308c\u306f\u30a2\u30d0\u30c9\u30f3\u3067\u306f\u306a\u304f\u672c\u4eba\u306e\u610f\u601d\u3067\u3044\u3044\u3093\u3060\u3088\u306a\uff1f\u4eca\u307e\u3067\u66f2\u304c\u308a\u306a\u308a\u306b\u3082\u7236\u3092\u6155\u3063\u3066\u308b\u611f\u3058\u3060\u3063\u305f\u306e\u3067\u3001\u3069\u3046\u3044\u3046\u611f\u60c5\u3067\u3053\u306e\u767a\u8a00\u3092\u3057\u3066\u3044\u308b\u306e\u304b\u304c\u63b4\u3081\u306a\u3044\u3002\u4e00\u5ea6\u3061\u3083\u3093\u3068\u3076\u3064\u304b … <\/p>\n

Read more » “2023\/3\/28(\u706b)”<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-4387","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/posts\/4387","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/comments?post=4387"}],"version-history":[{"count":10,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/posts\/4387\/revisions"}],"predecessor-version":[{"id":4397,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/posts\/4387\/revisions\/4397"}],"wp:attachment":[{"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/media?parent=4387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/categories?post=4387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/tags?post=4387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}