{"description":"\u671f\u5f85\u5024= \u3068\u3044\u3046\u3060\u3051\u306e\u8a71\u306a\u3093\u3067\u3059\u304c\u3001\u3053\u308c\u3057\u304b\u982d\u306b\u306a\u3044\u3068\u540c\u3058\u5f0f\u5909\u5f62\u306b\u6bce\u56de\u4e00\u751f\u3092\u8cbb\u3084\u3057\u3066\u3057\u307e\u3046\u306e\u3067\u5178\u578b\u7684\u306a\u7528\u6cd5\u3092\u30e1\u30e2\u3057\u3066\u304a\u304f\u3002 \u554f\u984c\uff1a S+1\u306e\u72b6\u614b\u304c\u3042\u308a\u3001\u72b6\u614b0\u304b\u3089\u59cb\u3081\u3066\u3001\u72b6\u614bS\u306b\u5230\u9054\u3057\u305f\u3089\u7d42\u4e86\u3002 1\u56de\u306e\u64cd\u4f5c\u3067\u72b6\u614bi\u304b\u3089\u72b6\u614bj\u306b\u9077\u79fb\u3059\u308b\u78ba\u7387\u304c\u306e\u3068\u304d\u3001\u7d42\u4e86\u3059\u308b\u307e\u3067\u306e\u64cd\u4f5c\u56de\u6570\u306e\u671f\u5f85\u5024\u306f\uff1f\u524d\u7f6e\u304d\uff1a \u30b0\u30e9\u30d5\u304cDAG\u2192DP\u3057\u308d \u672c\u984c\u306b\u5165\u308b\u524d\u306b\u5178\u578b\u554f\u984c\u3092\u4e00\u3064 \u554f\u984c\uff1a \u88cf\u304c\u51fa\u308b\u307e\u3067\u30b3\u30a4\u30f3\u30c8\u30b9\u3059\u308b\u3002\u671f\u5f85\u5024\u4f55\u56de\uff1f \u7b54\u3048\uff1a n\u56de\u76ee\u306e\u30b3\u30a4\u30f3\u30c8\u30b9\u3092\u3059\u308b\u78ba\u7387\u304c(1/2)^n\u3060\u304b\u3089\u3001\u5143\u306e\u554f\u984c\u306b\u623b\u308b \u306ei,j\u2260S\u3092\u4e26\u3079\u3066\u3067\u304d\u308b\u884c\u5217S\u00d7S\u884c\u5217\u3092P\u3068\u3059\u308b\u3068\u6c42\u3081\u308b\u671f\u5f85\u5024\u306f \u6c42\u307e\u3063\u305f\u3002 \u554f\u984c\uff12\uff1a S+1\u306e\u72b6\u614b\u304c\u3042\u308a\u3001\u72b6\u614b0\u304b\u3089\u59cb\u3081\u3066\u2026","url":"https://sugarknri.hatenablog.com/entry/2022/08/09/004829","author_url":"https://blog.hatena.ne.jp/sugarknri/","version":"1.0","height":"190","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsugarknri.hatenablog.com%2Fentry%2F2022%2F08%2F09%2F004829\" title=\"\u671f\u5f85\u5024 - \u30e1\u30e2\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","image_url":null,"published":"2022-08-09 00:48:29","provider_name":"Hatena Blog","type":"rich","author_name":"sugarknri","provider_url":"https://hatena.blog","blog_url":"https://sugarknri.hatenablog.com/","title":"\u671f\u5f85\u5024","categories":["\u30c6\u30af\u30cb\u30c3\u30af"],"blog_title":"\u30e1\u30e2","width":"100%"}