{"id":3441,"date":"2022-09-25T00:10:57","date_gmt":"2022-09-24T15:10:57","guid":{"rendered":"https:\/\/k.foolslab.net\/dailyreport\/?p=3441"},"modified":"2022-09-25T00:12:31","modified_gmt":"2022-09-24T15:12:31","slug":"2022-9-24","status":"publish","type":"post","link":"https:\/\/k.foolslab.net\/dailyreport\/2022-9-24\/","title":{"rendered":"2022\/9\/24(\u571f)"},"content":{"rendered":"\n<p>\u306a\u3093\u304b\u4e00\u65e5\u5bb6\u306b\u5f15\u304d\u3053\u3082\u3063\u3066\u3057\u307e\u3063\u305f\u3002\u5bb6\u306e\u4e2d\u3067\u30e9\u30b8\u30aa\u4f53\u64cd\u3050\u3089\u3044\u306e\u904b\u52d5\u306f\u3057\u305f\u304c\u3002\u660e\u65e5\u306f\u30b8\u30e7\u30ae\u30f3\u30b0\u304f\u3089\u3044\u3057\u305f\u3044\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\u95a2\u7bc0\u90e8\u306e\u808c\u306e\u8abf\u5b50\u304c\u3059\u3053\u3076\u308b\u60aa\u3044\u3002\u304b\u3055\u304b\u3055\u3059\u308b\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>\u4eca\u65e5\u89e3\u3044\u305f\u7af6\u30d7\u30ed\u306e\u554f\u984c\u3002<\/p>\n\n\n\n<p>ABC126-F: \u306a\u3093\u3068\u304b\u304b\u3093\u3068\u304b\u81ea\u529bAC\u3002\u304b\u306a\u308a\u60a9\u3093\u3060\u6319\u53e5\u3001\u6700\u7d42\u7684\u306a\u7b54\u3048\u306f\u30ae\u30e3\u30b0\u307f\u305f\u3044\u306a\u5929\u624d\u69cb\u7bc9\u3060\u3063\u305f\u3002<\/p>\n\n\n\n<p>\u307e\u305a$K\\geq 2^M$\u306e\u3068\u304d\u3001\u6570\u5217$a$\u306f$2^M$\u306e\u30d3\u30c3\u30c8\u30921\u306b\u3059\u308b\u3053\u3068\u81ea\u4f53\u3067\u304d\u306a\u3044\u306e\u3067\u4e0d\u53ef\u80fd\u3068\u3044\u3046\u3053\u3068\u304c\u5206\u304b\u308b\u3002<\/p>\n\n\n\n<p>\u305d\u308c\u304b\u3089$M=0$\u306e\u3068\u304d\u306f$K=0$\u306e\u3068\u304d\u306e\u307f\u53ef\u80fd\u3001$M=1$\u306e\u3068\u304d\u306f$K=0$\u306a\u3089\u3070\u53ef\u80fd\u3067$K=1$\u306a\u3089\u3070\u4e0d\u53ef\u80fd\u3068\u3044\u3046\u3053\u3068\u304c\u3061\u3087\u3063\u3068\u5b9f\u9a13\u3057\u3066\u307f\u308c\u3070\u5206\u304b\u308b\u3002<\/p>\n\n\n\n<p>\u305d\u3057\u3066$0\\leq K &lt; 2^M$\u304b\u3064$M\\geq 2$\u306e\u3068\u304d\u3001\u5b9f\u306f\u5fc5\u305a\u6761\u4ef6\u306b\u5408\u3046$a$\u304c\u69cb\u6210\u3067\u304d\u308b\u3002$M\\geq 2$\u306b\u304a\u3044\u3066$0\\ xor\\ 1\\ xor\\ 2\\ xor\\ &#8230;\\ xor\\ 2^M &#8211; 1$\u304c\u5fc5\u305a0\u306b\u306a\u308b\u3053\u3068\u306b\u6c17\u4ed8\u304f\u3068\u89e3\u3051\u308b\u3002<\/p>\n\n\n\n<p>$[0, 2^M)$\u306e\u3046\u3061K\u3092\u9664\u304f\u3082\u306e\u3092\u6607\u9806\u306b\u4e26\u3079\u305f\u6570\u5217\u3092$P$, \u964d\u9806\u306b\u4e26\u3079\u305f\u3082\u306e\u3092$Q$\u3068\u3057\u3066\u3001$P, K, Q, K$\u3068\u4e26\u3079\u308b\u3068\u3053\u306e\u6570\u5217\u306f\u6761\u4ef6\u3092\u6e80\u305f\u3057\u3066\u3044\u308b\u3002\u4f8b\u3048\u3070$M=3, K=2$\u3068\u3059\u308b\u3068<\/p>\n\n\n\n<p><code>(0 1 2 4 5 6 7) 3 (7 6 5 4 2 1 0) 3<\/code><\/p>\n\n\n\n<p>\u3068\u3044\u3063\u305f\u611f\u3058\u306b\u306a\u308b\u3002K\u4ee5\u5916\u306e\u6570\u5b57\u306b\u3064\u3044\u3066\u306f\u5168\u3066P\u3068Q\u306b\u542b\u307e\u308c\u3001XOR\u3067\u6253\u3061\u6d88\u3055\u308c\u305f\u7d50\u679cK\u3060\u3051\u3092\u631f\u3080\u3053\u3068\u306b\u306a\u308b\u306e\u3067\u6761\u4ef6\u3092\u6e80\u305f\u3059\u3002K\u306f\u6570\u5217Q\u3092\u631f\u3080\u304c\u3001\u3053\u308c\u306f$[0, 2^M)$\u304b\u3089$K$\u3060\u3051\u3092\u9664\u3044\u305f\u3082\u306e\u306e\u7dcfxor\u3067\u3042\u308a\u3001$[0, 2^M)$\u306e\u7dcfxor\u304c0\u3067\u3042\u308b\u3053\u3068\u3092\u8e0f\u307e\u3048\u308b\u3068\u3053\u306e\u5024\u306f$K$\u306b\u306a\u308b\u3002<\/p>\n\n\n\n<p>\u6c17\u4ed8\u3051\u3070\u5358\u7d14\u3060\u304c\u3001\u4e00\u4f53\u3069\u3046\u3084\u3063\u3066\u6c17\u3065\u3051\u308b\u3093\u3060\u3053\u308c\uff1f<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>ABC270\u306b\u53c2\u52a0\u3057\u305f\u3002<\/p>\n\n\n\n<p>A: 2\u9032\u6570\u3002<\/p>\n\n\n\n<p>B: \u4e01\u5be7\u306b\u5834\u5408\u5206\u3051\u3059\u308b\u3060\u3051\u3002<\/p>\n\n\n\n<p>C: \u3044\u3064\u3082\u9802\u70b91\u3092\u6839\u3068\u3057\u304c\u3061\u306a\u306e\u3067LCA\u3068\u304b\u304c\u4e00\u77ac\u982d\u306b\u3088\u304e\u3063\u305f\u304c\u3001\u666e\u901a\u306bX\u304bY\u3092\u6839\u306b\u3059\u308c\u3070\u3044\u3044\u3060\u3051\u3060\u3063\u305f\u3002<\/p>\n\n\n\n<p>D: \u8caa\u6b32\u6cd5\u3092\u3057\u305f\u304f\u306a\u3063\u305f\u304c\u5236\u7d04\u304b\u3089DP\u81ed\u304c\u3057\u305f\u306e\u3067\u3001DP\u306e\u5fc5\u8981\u304c\u3042\u308b\u3053\u3068\u306b\u6c17\u4ed8\u3051\u305f\u3002\u3061\u3083\u3093\u3068\u8caa\u6b32\u306e\u53cd\u4f8b\u3092\u8003\u3048\u305f\u308f\u3051\u3067\u306f\u306a\u3044\u304c\u3001\u306a\u3093\u304b\u5358\u7d14\u306b\u30c7\u30ab\u3044\u306e\u304b\u3089\u53d6\u308d\u3046\u3068\u3059\u308b\u3068\u5f8c\u306e\u9078\u629e\u80a2\u304c\u72ed\u307e\u308b\u3093\u3060\u308d\u3046\u3002<\/p>\n\n\n\n<p>DP[k]:=(\u6b8b\u308a\u306e\u77f3\u304ck\u500b\u306e\u72b6\u614b\u3067\u624b\u756a\u304c\u56de\u3063\u3066\u304d\u305f\u5834\u5408\u306e\u305d\u3053\u304b\u3089\u5897\u3084\u305b\u308b\u6700\u5927\u30b9\u30b3\u30a2, \u6700\u5927\u30b9\u30b3\u30a2\u3092\u5f97\u308b\u305f\u3081\u306e\u6700\u5584\u624b)<\/p>\n\n\n\n<p>\u3068\u3057\u3066\u7ba1\u7406\u3059\u308b\u3002<\/p>\n\n\n\n<p>E: \u5358\u7d14\u306b\u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u3059\u308b\u3068\u5f53\u7136TLE\u306a\u306e\u3067\u3001\u30ea\u30f3\u30b4\u306e\u6570\u304c\u540c\u3058\u30d0\u30b9\u30b1\u30c3\u30c8\u3092\u307e\u3068\u3081\u3066\u8003\u3048\u308b\u3002\u305d\u308c\u3060\u3051\u3060\u3068\u307e\u3060TLE\u3057\u3046\u308b\u306e\u3067\u3001\u307e\u3060\u30ea\u30f3\u30b4\u304c\u6b8b\u3063\u3066\u3044\u308b\u30d0\u30b9\u30b1\u30c3\u30c8\u306e\u6570\u3092\u7ba1\u7406\u3057\u306a\u304c\u30891\u5468\u5206\u3092\u307e\u3068\u3081\u3066\u8a08\u7b97\u3059\u308b\u3002\u6b21\u306e1\u9031\u3067\u7d42\u308f\u308b\u3068\u3044\u3046\u6bb5\u968e\u306b\u306a\u3063\u305f\u3089\u5358\u7d14\u306b\u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u3059\u308c\u3070\u3088\u3044\u3002\u30ea\u30f3\u30b4\u306e\u6570\u306e\u7a2e\u985e\u306f\u9ad8\u3005N\u500b\u306a\u306e\u3067$O(N)$\u3002<\/p>\n\n\n\n<p>F: \u3069\u3053\u304b\u3089\u3069\u3046\u898b\u3066\u3082\u6700\u5c0f\u5168\u57df\u6728\u554f\u984c\u3002\u7a7a\u6e2f\u3068\u6e2f\u3092\u8003\u616e\u3059\u308b\u305f\u3081\u306b\u3001\u7a7a\u3068\u6d77\u3092\u4eee\u60f3\u9802\u70b9\u3068\u3059\u308b\u3002<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\u5404\u5cf6\u3001\u7a7a\u3001\u6d77\u3092\u7d50\u3076\u6700\u5c0f\u5168\u57df\u6728<\/li><li>\u5404\u5cf6\u3001\u7a7a\u3092\u7d50\u3076\u6700\u5c0f\u5168\u57df\u6728<\/li><li>\u5404\u5cf6\u3001\u6d77\u3092\u7d50\u3076\u6700\u5c0f\u5168\u57df\u6728<\/li><li>\u5404\u5cf6\u3092\u9053\u8def\u306e\u307f\u3067\u7d50\u3076\u6700\u5c0f\u5168\u57df\u6728(\u5168\u57df\u6728\u306b\u306a\u3063\u3066\u3044\u306a\u3044\u5834\u5408\u304c\u3042\u308a\u3046\u308b\u306e\u3067\u78ba\u8a8d\u51e6\u7406\u3092\u5165\u308c\u308b)<\/li><\/ul>\n\n\n\n<p>\u4e0a\u306e4\u901a\u308a\u5168\u3066\u306e\u6700\u5c0f\u5024\u304c\u7b54\u3048\u306b\u306a\u308b\u3002E\u3088\u308a\u3082\u7c21\u5358\u3002\u3057\u304b\u3057\u3057\u3087\u3046\u3082\u306a\u3044\u30df\u30b9\u3067\u30ed\u30b9\u3063\u3066\u3057\u307e\u3063\u305f\u3002<\/p>\n\n\n\n<p>G: \u5f0f\u5909\u5f62\u3059\u308c\u3070\u5206\u304b\u308b\u901a\u308a\u306e\u96e2\u6563\u5bfe\u6570\u554f\u984c\u3002\u306a\u3093\u304b\u96e2\u6563\u5bfe\u6570\u306f$O(\\sqrt{P})$\u3067\u89e3\u3051\u308b\u3082\u306e\u3089\u3057\u3044\u3002\u5f8c\u3067upsolve\u3057\u3066\u304a\u3053\u3046\u3002\u3088\u304f\u898b\u308b\u3068A\u22661\u306e\u5834\u5408\u306f\u96e2\u6563\u5bfe\u6570\u3069\u3053\u308d\u3067\u306f\u306a\u3044\u306e\u3067\u7279\u5225\u6271\u3044\u3057\u306a\u3051\u308c\u3070\u306a\u3089\u306a\u3044\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u306a\u3093\u304b\u4e00\u65e5\u5bb6\u306b\u5f15\u304d\u3053\u3082\u3063\u3066\u3057\u307e\u3063\u305f\u3002\u5bb6\u306e\u4e2d\u3067\u30e9\u30b8\u30aa\u4f53\u64cd\u3050\u3089\u3044\u306e\u904b\u52d5\u306f\u3057\u305f\u304c\u3002\u660e\u65e5\u306f\u30b8\u30e7\u30ae\u30f3\u30b0\u304f\u3089\u3044\u3057\u305f\u3044\u3002 \u95a2\u7bc0\u90e8\u306e\u808c\u306e\u8abf\u5b50\u304c\u3059\u3053\u3076\u308b\u60aa\u3044\u3002\u304b\u3055\u304b\u3055\u3059\u308b\u3002 \u4eca\u65e5\u89e3\u3044\u305f\u7af6\u30d7\u30ed\u306e\u554f\u984c\u3002 ABC126-F: \u306a\u3093\u3068\u304b\u304b\u3093\u3068\u304b\u81ea &hellip; <\/p>\n<div><a href=\"https:\/\/k.foolslab.net\/dailyreport\/2022-9-24\/\" class=\"more\">Read more &raquo;<span class=\"screen-reader-text\"> &#8220;2022\/9\/24(\u571f)&#8221;<\/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-3441","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/posts\/3441","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=3441"}],"version-history":[{"count":9,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/posts\/3441\/revisions"}],"predecessor-version":[{"id":3450,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/posts\/3441\/revisions\/3450"}],"wp:attachment":[{"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/media?parent=3441"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/categories?post=3441"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/k.foolslab.net\/dailyreport\/wp-json\/wp\/v2\/tags?post=3441"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}