{"id":1009,"date":"2022-05-15T15:02:32","date_gmt":"2022-05-15T07:02:32","guid":{"rendered":"https:\/\/blog.cruciferslab.net\/?p=1009"},"modified":"2022-05-15T15:02:32","modified_gmt":"2022-05-15T07:02:32","slug":"gcj-2022-round-2","status":"publish","type":"post","link":"https:\/\/blog.cruciferslab.net\/?p=1009","title":{"rendered":"GCJ 2022 Round 2"},"content":{"rendered":"\n

\u6158\u70c8\u7684\u4e00\u5834\u6bd4\u8cfd\u2026\u2026\u6158\u70c8\u5230\u539f\u672c\u4ee5\u70ba\u6211\u61c9\u8a72\u6c92\u6709\u6649\u7d1a\u6a5f\u6703\u7684\uff0c\u4f46\u7d50\u679c\u958b\u734e\u4e4b\u5f8c\u537b\u767c\u73fe\u53ea\u8981\u6700\u5f8c\u65e9\u500b\u5341\u4e94\u5206\u9418\u6c7a\u5b9a\u653e\u68c4\u6771\u897f\u5c31\u80fd\u6649\u7d1a\u4e86\u3002<\/p>\n\n\n\n

\u591a\u6158\uff1f\u9019\u6b21\u7684\u6649\u7d1a\u7dda\u662f 25\/100<\/strong> (+1:19:12)\uff0c\u5c0d\u61c9\u901a\u904e\u984c\u76ee\u662f Q1 \u53ca Q2 \u5c0f\u2026\u2026<\/p>\n\n\n\n

\u6211\u81ea\u5df1\u7684\u6210\u7e3e\u4e5f\u662f 25\/100\uff0c\u4e0d\u904e\u679c\u7136\u505a\u984c\u76ee\u6c92\u6709\u9019\u9ebc\u9806\u624b\u4e86\uff0c\u52a0\u4e0a Q1 \u7684\u4e00\u6b21\u7f70\u6642\u6211\u7684\u6642\u9593\u662f +1:43:05\uff0c\u6392\u5728\u4e86 1142 \u540d\u3002<\/p>\n\n\n\n

\u6163\u4f8b\u6210\u7e3e\u622a\u5716\u4ee5\u4e0b\u6709\u96f7\u3002<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n\n\n\n\n

Q1. Spiraling into Control<\/h2>\n\n\n\n

\u9019\u984c\u5176\u5be6\u5f88\u5feb\u5c31\u6709\u60f3\u6cd5\uff0c\u4f46\u662f\u7d30\u7bc0\u8655\u7406\u4e0a\u9084\u662f\u8b93\u6211\u82b1\u4e86\u597d\u4e45\u6642\u9593\uff0c\u9084\u5403\u4e86\u4e00\u6b21 WA\u3002<\/p>\n\n\n\n

\u9996\u5148\u5f88\u5bb9\u6613\u5f97\u5230\u6709\u89e3\u7684\u5145\u8981\u689d\u4ef6\uff1a\u6b65\u6578 K \u662f\u5076\u6578\uff0c\u4e14\u81f3\u5c11\u662f N-1\u3002\u5076\u6578\u9019\u4ef6\u4e8b\u5c07\u76e4\u9762\u5857\u6210\u897f\u6d0b\u68cb\u76e4\u5c31\u5bb9\u6613\u8b49\u51fa\u4e86\uff0c\u9019\u88e1\u5c31\u7565\u904e\uff1b\u4e26\u4e14\u5f9e\u9019\u88e1\u4e5f\u80fd\u7c21\u55ae\u69cb\u9020\u51fa\u89e3\u3002\u9019\u984c\u7684\u96e3\u9ede\u5176\u5be6\u5728\u65bc\u8981\u600e\u9ebc\u628a\u89e3\u8f38\u51fa\uff1a\u9019\u984c\u8981\u6c42\u6211\u5011\u7684\u8f38\u51fa\u53ea\u5305\u542b\u8df3\u865f\u7684\u6b65\uff0c\u56e0\u6b64\u5f97\u8981\u5f9e\u982d\u5206\u6790\u4e00\u904d\u69cb\u9020\u51fa\u4f86\u7684\u89e3\u7684\u5be6\u969b\u6b65\u6578\u624d\u884c\u3002<\/p>\n\n\n\n

\u6211\u69cb\u9020\u7684\u89e3\u662f\u9019\u6a23\u5b50\u7684\uff1a\u9996\u5148\uff0c\u5982\u679c\u6b65\u6578\u591a\u5230\u8d70\u5b8c\u4e00\u5708\u9084\u80fd\u6709\u89e3\uff0c\u90a3\u5c31\u628a\u90a3\u5708\u525d\u6389\uff0c\u5c0d\u88e1\u9762\u8f38\u51fa\u89e3\u5373\u53ef\u3002\u4f8b\u5982 5 18\uff0c\u5728\u8d70\u5b8c 16 \u6b65\u5230 17 \u5f8c\u9084\u5269\u5169\u6b65\uff0c\u800c 3 2 \u662f\u6709\u89e3\u7684\uff0c\u56e0\u6b64\u9019\u500b\u89e3\u5c31\u7b49\u65bc 3 2 \u4f46\u6240\u6709\u6578\u5b57\u90fd\u52a0 16\u3002\u5269\u4e0b\u7684\u6b65\u9a5f\u6211\u662f\u9019\u6a23\u69cb\u9020\u7684\uff1a<\/p>\n\n\n\n

  • 5 4\uff1a1\u21922\u21923\u21e818\u21e825<\/li>
  • 5 6\uff1a1\u21922\u21923\u21924\u21e819\u219220\u21e825<\/li>
  • 5 8\uff1a1\u21922\u21923\u21924\u21925\u21926\u21927\u21e820\u21e825<\/li>
  • 5 10\uff1a1\u21922\u21923\u21924\u21925\u21926\u21927\u21928\u21e821\u219222\u21e825<\/li>
  • 5 12\uff1a1\u21922\u21923\u21924\u21925\u21926\u21927\u21928\u21929\u219210\u219211\u21e822\u21e825<\/li>
  • 5 14\uff1a1\u21922\u21923\u21924\u21925\u21926\u21927\u21928\u21929\u219210\u219211\u219212\u21e823\u219224\u219225<\/li>
  • 5 16\uff1a1\u21922\u21923\u21924\u21925\u21926\u21927\u21928\u21929\u219210\u219211\u219212\u219213\u219214\u219215\u21e824\u219225<\/li><\/ul>\n\n\n\n

    \u6a19 \u21e8 \u7684\u662f\u8df3\u865f\u6b65\u3002\u9019\u4e9b\u6b65\u53ef\u7531\u5b83\u5011\u7b2c\u4e00\u6b65\u5728\u54ea\u4e00\u689d\u908a\u8f49\u5f4e\u5206\u985e\uff0c\u56e0\u70ba\u5728\u54ea\u908a\u8f49\u5f4e\u5f71\u97ff\u5230\u8f49\u5f4e\u5f8c\u7684\u6578\u5b57\u5dee\uff1a5 4 \u7684\u5f4e\u5dee 15\uff0c5 8 \u7684\u5f4e\u53ea\u5dee 13\uff0c5 12 \u7684\u5f4e\u53ea\u5dee 11\uff0c5 16 \u7684\u5f4e\u5c31\u53ea\u5dee 9 \u4e86\u3002\u7576\u7136\uff0c\u8f49\u5f4e\u5f8c\u9084\u8981\u5224\u65b7\u9019\u6b21\u8f49\u5f4e\u662f\u4e0d\u662f\u6b63\u597d\u63a5\u4e0a\u5167\u5c64\u9806\u8f49\u7684\u8def\u4e86\uff0c\u9019\u6a23\u5f8c\u9762\u5c31\u53ea\u5269\u76f4\u5f80\u4e2d\u5fc3\u7684\u76f4\u8def\uff1b\u4ee5\u53ca\u5224\u65b7\u8df3\u865f\u6b65\u7684\u500b\u6578 (\u5b83\u4e0d\u662f\u5728\u8d70\u5b8c\u4e00\u5708\u5c31\u6e1b\u4e00\u4e86\uff1b\u50cf\u4e0a\u9762 5 12 \u9084\u6709\u5169\u6b65\uff0c5 14 \u5c31\u5269\u4e00\u6b65\u4e86\u3002\u76f4\u63a5\u7406\u7531\u662f\u6700\u5167\u5c64\u5f80\u4e2d\u5fc3\u7684\u8def\u5728\u9019\u88e1\u8b8a\u6210\u9806\u8f49\u6c92\u6709\u8df3\u865f\u4e86\u7684\u95dc\u4fc2\u3002)<\/p>\n\n\n\n

    \u800c\u6211\u7684 WA\u2026\u2026\u5247\u662f\u5728\u50cf 5 16 \u9019\u7a2e\u6700\u5f8c\u4e00\u7d44\u7684\u908a\u4e0a\u9032\u5834\u7684\u8def\u7dda\u8a08\u7b97\u51fa\u554f\u984c\u30025 16 \u9084\u6c92\u4e8b\uff0c\u51fa\u4e8b\u7684\u662f\u50cf 7 26 \u9019\u7a2e\u8f38\u5165\uff1a\u56e0\u70ba\u6700\u5f8c\u4e00\u7d44\u9032\u5834\u908a\u7684\u5167\u5c64\u9806\u8f49\u63a5\u7684\u5224\u65b7\u689d\u4ef6\u4e0d\u540c\uff0c\u8981\u5206\u958b\u5beb\u624d\u884c\u3002<\/p>\n\n\n\n

    Q2. Pixelated Circle<\/h2>\n\n\n\n

    \u2026\u2026\u679c\u7136\u5206\u6790\u4e0d\u5920\uff0c\u539f\u672c\u4ee5\u70ba\u53ea\u6578\u4e00\u500b\u516b\u5206\u4e4b\u4e00\u6247\u5f62\u88e1\u7684\u9ede\u5c31\u5920\u4e86\u7684\u3002<\/p>\n\n\n\n

    \u4e0d\u904e\u6211\u5012\u662f\u63a8\u5c0e\u51fa\u4e86\u4e00\u500b\u5ea7\u6a19\u662f\u4e0d\u662f\u6703\u662f\u7a7a\u9ede\u7684\u689d\u4ef6\u4e86\uff1a\u82e5\u5169\u5ea7\u6a19\u7684\u7d55\u5c0d\u503c\u662f \\(x, y\\) \u4e14\u4ee4 \\(x<y\\)\uff0c\u5247\u7576\u4e14\u50c5\u7576\u7bc4\u570d \\([x^2+(y-0.5)^2,x^2+(y+0.5)^2]\\) \u4e2d\u6c92\u6709\u5e73\u65b9\u6578\u6642\uff0c(x, y) \u4e0d\u6703\u88ab\u932f\u7684\u5be6\u4f5c\u7d66\u5857\u5230\u8272\u3002\u6211\u5beb\u4e0a\u53bb\u7684\u7a0b\u5f0f\u5c31\u662f\u57fa\u672c\u5be6\u4f5c\u9019\u500b\u6aa2\u67e5\uff0c\u518d\u52a0\u4e0a\u89c0\u5bdf\u5230\u53ea\u8981 \\(\\left\\lceil x^2+(y-0.5)^2\\right\\rceil=x^2+y^2-y+1\\) \u6b64\u503c\u7b49\u65bc \\(y^2\\) \u7684\u8a71\uff0c\u5c0d\u66f4\u5927\u7684 y \u5c31\u90fd\u6703\u5857\u5230\u8272\u4e86\u7684\u5224\u65b7\uff0c\u628a\u9019\u500b\u6aa2\u67e5\u5207\u5728 \\(y=\\min(x^2+1,\\sqrt{r^2-x^2})\\)\u3002\u4e0d\u904e\u770b\u4f86\u679c\u7136\u9084\u662f\u4e0d\u5920\u2026\u2026<\/p>\n\n\n\n

    Q3. Saving the Jelly & Q4. I, O Bot<\/h2>\n\n\n\n

    \u9019\u5169\u984c\u6700\u5f8c\u90fd\u6c92\u505a\uff0c\u4f46 Q3 \u6709\u4e00\u6b21\u5617\u8a66\u3002\u9019\u5c31\u662f\u6700\u958b\u59cb\u6642\u6240\u8aaa\u7684\u6c7a\u7b56\uff1a\u6211\u76f4\u5230\u7d42\u5834\u524d 15 \u5206\u9418\u624d\u6c7a\u5b9a\u653e\u6389 Q3 \u5927\uff0c\u5beb\u500b Q3 \u5c0f\u80fd\u904e\u7684\u89e3\uff0c\u7d50\u679c\u521d\u7248\u5b8c\u6210\u6642\u6b63\u597d\u7528\u5b8c\u9019 15 \u5206\u9418\uff0c\u60f3\u7576\u7136\u723e\u6c92\u6709\u901a\u904e\uff0d\uff0d\u7136\u5f8c\u8cfd\u5f8c\u53c8\u82b1\u4e86\u500b 15 \u5206\u9418\u4fee\u6210\u5230 Q3 \u5c0f\u80fd\u904e\u7684\u7b54\u6848\u4e86\u3002\u99ac\u5f8c\u70ae\u4f86\u770b\uff0c\u53ea\u8981\u65e9 15 \u5206\u9418\u6c7a\u5b9a\u5beb\u9019\u7248\uff0c\u6211\u80fd\u62ff\u5230\u9019 10 \u5206\u5c31\u80fd\u6649\u7d1a\u4e86\u3002Oh Well\u3002<\/p>\n\n\n\n

    \u6703\u5361\u984c\u9019\u9ebc\u4e45\u5176\u5be6\u662f\u6211\u540c\u6642\u5728\u8a55\u4f30\u8981\u89e3 Q3 Q4 \u54ea\u4e00\u984c (Q2 \u9001\u4e0a\u53bb\u4e4b\u5f8c\u9084\u6709\u4e00\u5c0f\u6642\u5de6\u53f3)\uff0c\u4e0d\u904e Q3 \u5b8c\u5168\u6c92\u6709\u60f3\u6cd5\uff0c\u5012\u662f Q4 \u6709\u4e86\u4e00\u500b\u6a21\u7cca\u7684\u6982\u5ff5\u597d\u50cf\u9700\u8981\u9032\u884c\u4e00\u4e9b\u914d\u5c0d\uff0c\u6240\u4ee5\u53ef\u80fd\u662f\u500b network flow \u984c\u3002\u5728\u4ed4\u7d30\u7814\u7a76 Q4 \u7684\u914d\u5c0d\u7d30\u7bc0\u6642\u624d\u767c\u73fe\u4e0d\u5c0d\uff0c\u9019\u7d30\u7bc0\u6709\u9ede\u591a\uff0c\u597d\u50cf\u4e0d\u5bb9\u6613\u8f49\u6210 flow\uff0c\u52a0\u4e0a\u6211\u4e5f\u5e7e\u767e\u5e74 (!) \u6c92\u5beb flow \u4e86\u6240\u4ee5\u9084\u662f\u56de\u982d\u4f86\u60f3 Q3 \u5230\u5e95\u8a72\u600e\u9ebc\u8d70\u3002\u53ea\u662f\u9019\u500b\u914d\u5c0d\u984c\u7684\u689d\u4ef6\u5f88\u4e0d\u4e00\u822c\uff0c\u800c\u4e14 N \u4e0a\u9650\u4e5f\u53ea\u6709 1000\uff0c\u770b\u8d77\u4f86\u4e00\u526f\u5c31\u662f\u4e0a\u770b\u4e09\u6b21\u65b9\u7684\u6f14\u7b97\u6cd5 orz \u56e0\u6b64\u624d\u6709\u6700\u5f8c\u9019\u500b\u6c7a\u5b9a\u53ea\u5beb N \u5230 10 \u7684\u89e3\uff0c\u7d50\u679c\u770b\u8d77\u4f86\u662f\u6642\u9593\u592a\u6025\u6c92\u7d30\u60f3\uff0c\u6211\u76f4\u63a5\u62ff\u4e86 next_permutation<\/code> \u53bb\u786c\u8a66 10! \u7a2e\u7d44\u5408\uff0c\u6c92\u6ce8\u610f\u5230\u7528\u6700\u7c21\u55ae\u7684 DFS \u586b\u6578\u7368\u641c\u5c0b\u6cd5\u5c31\u884c\u4e86\u3002<\/p>\n\n\n\n

    \u5c0f\u7d50<\/h2>\n\n\n\n

    \u8aaa\u8d77\u4f86\u6211\u9019\u5e7e\u5e74\u6253 GCJ \u5176\u5be6\u4e00\u534a\u662f\u88f8\u53c3\u8cfd\uff0c\u7562\u7adf\u56de\u4e0d\u53bb\u5927\u5b78\u6642\u671f\u90a3\u7a2e\u53ef\u4ee5\u5929\u5929\u7814\u7a76\u7af6\u8cfd\u7684\u751f\u6d3b\uff0c\u53ea\u6709\u5e73\u6642\u7684 Project Euler \u9084\u6709\u4e00\u9ede\u89e3\u984c\u523a\u6fc0\u800c\u5df2\uff1b\u4e0d\u904e\u770b\u4f86\u4e5f\u771f\u7684\u662f\u8001\u4e86\uff0c\u9023\u7e8c\u5169\u5e74\u6c7a\u7b56\u5931\u8aa4\u5728 R2 \u843d\u99ac\u3002<\/p>\n\n\n\n

    \u4e0b\u6b21\u662f\u4e0b\u9031\u7684 GKS Round C\uff0c\u4e0d\u904e\u9031\u65e5\u665a\u4e03\u9019\u500b\u6642\u9593\u6709\u4e00\u9ede\u9ede\u56e7\u5c31\u662f\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"

    \u6158\u70c8\u7684\u4e00\u5834\u6bd4\u8cfd\u2026\u2026\u6158\u70c8\u5230\u539f\u672c\u4ee5\u70ba\u6211\u61c9\u8a72\u6c92\u6709\u6649\u7d1a\u6a5f\u6703\u7684\uff0c\u4f46\u7d50\u679c\u958b\u734e\u4e4b\u5f8c\u537b\u767c\u73fe\u53ea\u8981\u6700\u5f8c\u65e9\u500b\u5341\u4e94\u5206\u9418\u6c7a\u5b9a\u653e\u68c4\u6771\u897f\u5c31\u80fd […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,4],"tags":[],"class_list":["post-1009","post","type-post","status-publish","format-standard","hentry","category-gcj","category-programming"],"_links":{"self":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts\/1009","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1009"}],"version-history":[{"count":4,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts\/1009\/revisions"}],"predecessor-version":[{"id":1014,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=\/wp\/v2\/posts\/1009\/revisions\/1014"}],"wp:attachment":[{"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1009"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1009"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.cruciferslab.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1009"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}