{"blog_title":"\u305d\u306e\u3046\u3061\u8ab0\u304b\u306e\u5f79\u306b\u7acb\u3064","image_url":"https://cdn.blog.st-hatena.com/images/theme/og-image-1500.png","url":"https://for-no-one.hatenablog.com/entry/2021/09/05/040000","provider_url":"https://hatena.blog","title":"\u7af6\u30d7\u30ed\u30c1\u30e3\u30ec\u30f3\u30b8\u4f9b\u990a\u4f1a\u5834: AtCoder Beginner Contest 217 F - Make Pair","author_name":"n00ka","categories":["\u7af6\u6280\u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0","AtCoder","DP"],"published":"2021-09-05 04:00:00","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Ffor-no-one.hatenablog.com%2Fentry%2F2021%2F09%2F05%2F040000\" title=\"\u7af6\u30d7\u30ed\u30c1\u30e3\u30ec\u30f3\u30b8\u4f9b\u990a\u4f1a\u5834: AtCoder Beginner Contest 217 F - Make Pair - \u305d\u306e\u3046\u3061\u8ab0\u304b\u306e\u5f79\u306b\u7acb\u3064\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","version":"1.0","blog_url":"https://for-no-one.hatenablog.com/","height":"190","description":"\u30b3\u30f3\u30c6\u30b9\u30c8\u3067\u306e\u6642\u9593\u5207\u308c\u3084\u89e3\u3051\u306a\u304b\u3063\u305f\u904e\u53bb\u554f\u3092\u632f\u308a\u8fd4\u3063\u3066\u4f9b\u990a\u3057\u3066\u3044\u304f \u554f\u984c Difficulty: 1954 (\u8a18\u4e8b\u4f5c\u6210\u6642\u70b9) \u4f9b\u990a \u89e3\u6cd5 $N$ \u7d44\u306e\u30da\u30a2\u3092\u4f5c\u3063\u305f\u3068\u304d\u3001\u5404\u30da\u30a2\u306f\u5fc5\u305a\u5076\u6570\u3068\u5947\u6570\u306e\u7d44\u3067\u3042\u308b \u4ee5\u964d\u306f $A_{i}, B_{i}$ \u306e\u5076\u5947\u304c\u7570\u306a\u308b\u3053\u3068\u3092\u524d\u63d0\u306b\u9032\u3081\u308b $u$ \u304b\u3089\u59cb\u307e\u308b\u9023\u7d9a\u3059\u308b $2n$ \u4eba\u306b\u3064\u3044\u3066 $n$ \u7d44\u306e\u30da\u30a2\u3092\u4f5c\u308b\u624b\u9806\u306e\u5834\u5408\u306e\u6570\u3092 $\\mathit{DP}_{u, n}$ \u3068\u3059\u308b \u4efb\u610f\u306e $u$ \u306b\u3064\u3044\u3066 $\\mathit{DP}_{u, 0} = 1$ \u3068\u3059\u308b $n = 1, \\dots, N$ \u306b\u3064\u3044\u3066\u4ee5\u4e0b\u306e\u3088\u3046\u306bDP\u8868\u3092\u66f4\u65b0\u3059\u308b $u = 1, \\dots,\u2026","type":"rich","author_url":"https://blog.hatena.ne.jp/n00ka/","width":"100%","provider_name":"Hatena Blog"}