{"provider_url":"https://hatena.blog","provider_name":"Hatena Blog","author_url":"https://blog.hatena.ne.jp/pm4/","title":"ABC201-E  Xor Distances ","blog_title":"\u7af6\u30d7\u30ed\u899a\u66f8","type":"rich","version":"1.0","url":"https://pm4.hatenadiary.jp/entry/2021/05/18/201230","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpm4.hatenadiary.jp%2Fentry%2F2021%2F05%2F18%2F201230\" title=\"ABC201-E  Xor Distances  - \u7af6\u30d7\u30ed\u899a\u66f8\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","author_name":"pm4","blog_url":"https://pm4.hatenadiary.jp/","categories":[],"description":"\u672c\u756a\u3067\u89e3\u3051\u305a\u3002\u91cd\u307f\u3092\u6841\u3054\u3068\u306b\u5206\u89e3\u3059\u308b\u3068\u3044\u3046\u767a\u60f3\u304c\u306a\u304b\u3063\u305f \u3010\u554f\u984c\u3011 \u91cd\u307f\u4ed8\u304d\u6728\u304c\u4e0e\u3048\u3089\u308c\u308b\u3002 dist(i, j) = i\u304b\u3089j\u3078\u306e\u6700\u77ed\u30d1\u30b9\u306b\u542b\u307e\u308c\u308b\u8fba\u3059\u3079\u3066\u306e\u91cd\u307f\u306eXOR \u3059\u3079\u3066\u306ei ,j(i<j)\u306b\u3064\u3044\u3066dist\u306e\u7dcf\u548c\u3092\u6c42\u3081\u3088 \u3010\u5fd8\u308c\u304c\u3061\u306a\u77e5\u8b58\u3011 \u7dcf\u548c\u306f\u6841\u3054\u3068\u306b\u72ec\u7acb\u3057\u3066\u8db3\u3057\u5408\u308f\u305b\u3089\u308c\u308b \u4f8b\uff1a123+789 = 1*10^2+7*10^2+2*10^1+8*10^1+3^10^0+9*10^0 \u3010\u5178\u578b\u30dd\u30a4\u30f3\u30c8\u3011 XOR => \u6841\u3054\u3068\u306b\u8003\u3048\u308b \u3010\u65b9\u91dd\u3011 \u611a\u76f4\u306bdist(i,j)\u3092\u5168\u5217\u6319\u3068\u3057\u3088\u3046\u3068\u3059\u308b\u3068\u6700\u4f4e\u3067\u3082O(N^2)\u3068\u306a\u308a\u3001\u5168\u7136\u9593\u306b\u5408\u308f\u306a\u3044\u3002 \u307e\u305f\u3001\u305d\u308c\u305e\u308c\u306edist(i, j)\u3082\u9ad8\u901f\u306b\u6c42\u2026","published":"2021-05-18 20:12:30","width":"100%","image_url":"https://cdn-ak.f.st-hatena.com/images/fotolife/p/pm4/20210518/20210518203102.png","height":"190"}