{"author_name":"mayokoex","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F05%2F01%2F194329\" title=\"AtCoder Regular Contest 052 C - \u9ad8\u6a4b\u304f\u3093\u3068\u4e0d\u601d\u8b70\u306a\u9053 - mayoko\u2019s diary\" 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","image_url":null,"published":"2016-05-01 19:43:29","provider_url":"https://hatena.blog","provider_name":"Hatena Blog","url":"https://mayokoex.hatenablog.com/entry/2016/05/01/194329","author_url":"https://blog.hatena.ne.jp/mayokoex/","blog_title":"mayoko\u2019s diary","categories":["AtCoder"],"height":"190","title":"AtCoder Regular Contest 052 C - \u9ad8\u6a4b\u304f\u3093\u3068\u4e0d\u601d\u8b70\u306a\u9053","width":"100%","type":"rich","blog_url":"https://mayokoex.hatenablog.com/","description":"\u554f\u984c arc052.contest.atcoder.jp \u89e3\u6cd5 \u307e\u305a\u81ea\u660e\u306a\u89e3\u6cd5\u3068\u3057\u3066, d[v][b] = (\u9802\u70b9 v \u307e\u3067\u306b, b \u56de\u30bf\u30a4\u30d7 B \u306e\u9053\u3092\u901a\u308b\u5834\u5408\u306e\u6700\u77ed\u8ddd\u96e2)\u3068\u3044\u3046\u306e\u304c\u3042\u308a\u307e\u3059\u3002b \u306f N \u3088\u308a\u5927\u304d\u304b\u3063\u305f\u3089\u3069\u3053\u304b\u306e\u9802\u70b9\u3092\u8907\u6570\u56de\u901a\u3063\u3066\u3044\u308b\u3053\u3068\u306b\u306a\u308b\u306e\u3067, \u9802\u70b9\u306e\u500b\u6570\u306f O(N^2) \u3067\u30c0\u30a4\u30af\u30b9\u30c8\u30e9\u3092\u3059\u308c\u3070\u826f\u3044\u3067\u3059\u3002\u3053\u308c\u3060\u3068\u3082\u3061\u308d\u3093 TLE, MLE \u3092\u3059\u308b\u3093\u3067\u3059\u304c, \u3053\u308c\u3092\u5de5\u592b\u3059\u308b\u3053\u3068\u3067\u89e3\u304c\u5f97\u3089\u308c\u307e\u3059\u3002need[v] = (\u9802\u70b9 v \u307e\u3067\u884c\u304f\u306e\u306b\u6700\u4f4e\u9650\u5fc5\u8981\u306a B \u306e\u8fba\u306e\u672c\u6570)\u3068\u3044\u3046\u306e\u3092\u524d\u8a08\u7b97\u3057\u3066\u304a\u304d\u307e\u3059\u3002 \u3059\u308b\u3068, need[v] \u3088\u308a\u3082 SIZE = 1.5*sqrt(N) \u672c\u2026"}