\u30b5\u30a4\u30c8\u79fb\u884c\u306e\u305f\u3081\u306e\u6e96\u5099\u3092\u771f\u9762\u76ee\u306b\u9032\u3081\u305f\u3002Vulkan\u5165\u9580\u3092\u3082\u3046\u3061\u3087\u3063\u3068\u66f8\u304d\u9032\u3081\u3066\u304b\u3089\u3068\u304b\u8a00\u3063\u3066\u3044\u305f\u304c\u3001\u3069\u3046\u8003\u3048\u3066\u3082\u305d\u3093\u306a\u306e\u5f85\u3063\u3066\u305f\u3089\u3044\u304f\u3089\u3067\u3082\u6642\u9593\u304c\u7d4c\u3064\u3057\u3001\u65e9\u304f\u51fa\u3059\u3079\u304d\u3002<\/p>\n\n\n\n
ABC298\u306b\u51fa\u305f\u3002\u304b\u306a\u308a\u5931\u6557\u3057\u305f\u3002E\u304c\u89e3\u3051\u306a\u304b\u3063\u305f\u306e\u304c\u75db\u3044\u3002<\/p>\n\n\n\n
A: \u3084\u308b\u3060\u3051<\/p>\n\n\n\n
B: \u3084\u308b\u3060\u3051<\/p>\n\n\n\n
C: \u7bb1\u306b\u5165\u3063\u3066\u3044\u308b\u30ab\u30fc\u30c9\u306e\u756a\u53f7\u3068\u3042\u308b\u756a\u53f7\u306e\u30ab\u30fc\u30c9\u306e\u5165\u3063\u3066\u3044\u308b\u7bb1\u3092\u305d\u308c\u305e\u308cmultiset\u3068set\u3067\u7ba1\u7406\u3059\u308b\u3002<\/p>\n\n\n\n
D: \u30af\u30a8\u30ea1\u304c\u6765\u305f\u3068\u304d\u306f10\u500d\u3057\u3066x\u3092\u8db3\u3059\u3002\u30af\u30a8\u30ea2\u304c\u6765\u305f\u3068\u304d\u306f(\u5148\u982d\u306e\u6570\u5b57)\u00d710^(\u6587\u5b57\u6570-1)\u3092\u5f15\u304f\u3002\u5f8c\u308d\u306b\u7e4b\u3052\u3066\u5148\u982d\u304b\u3089\u51fa\u3059\u306e\u3067\u5404\u6570\u5b57\u306f\u30ad\u30e5\u30fc\u3067\u7ba1\u7406\u3059\u308c\u3070\u5341\u5206\u3002<\/p>\n\n\n\n
E: \u306a\u3093\u304b\u3054\u3061\u3083\u3054\u3061\u3083\u3084\u3063\u3066\u89e3\u3051\u306a\u304b\u3063\u305f\u3002\u9ad8\u6a4b\u541b\u9752\u6728\u541b\u305d\u308c\u305e\u308c\u306b\u3064\u3044\u3066i\u56de\u76ee\u306e\u64cd\u4f5c\u6642\u306b\u30de\u30b9j\u306b\u3044\u308b\u30d1\u30bf\u30fc\u30f3\u6570\u3001\u3068\u304b\u3092\u8a08\u7b97\u3059\u308b\u3053\u3068\u306f\u3067\u304d\u305f\u306e\u3060\u304c\u3001\u4f55\u3092\u5206\u6bcd\u3068\u3057\u3066\u898b\u308b\u3079\u304d\u306a\u306e\u304b\u3092\u3061\u3083\u3093\u3068\u8003\u3048\u304d\u308c\u306a\u304b\u3063\u305f\u3002<\/p>\n\n\n\n
F: R\u884cC\u5217\u306e\u7dcf\u548cS\u306f(\u884cR\u306e\u7dcf\u548c)+(\u5217C\u306e\u7dcf\u548c)-(\u30de\u30b9R,C\u306b\u66f8\u3044\u3066\u3042\u308b\u6570\u5b57)\u3067\u6c42\u307e\u308b\u3002\u6570\u5b57\u304c1\u304b\u6240\u4ee5\u4e0a\u66f8\u3044\u3066\u3042\u308b\u884c\u306f\u9ad8\u3005N\u884c\u4ee5\u4e0b\u306a\u306e\u3067\u3001\u5404\u884c\u306b\u3064\u3044\u3066\u3082\u3063\u3068\u3082S\u304c\u5927\u304d\u304f\u306a\u308b\u5217\u3092\u9ad8\u901f\u306b\u898b\u3064\u3051\u3089\u308c\u308c\u3070\u3088\u3044\u3002<\/p>\n\n\n\n
RMQ\u306e\u51fa\u6765\u308b\u30bb\u30b0\u6728\u306b\u5404\u5217\u306e\u7dcf\u548c\u3092\u66f8\u304d\u8fbc\u3080\u3002\u3042\u308b\u884c\u3092\u8003\u3048\u308b\u3068\u304d\u3001\u305d\u306e\u884c\u306e\u4e2d\u3067\u6570\u5b57\u304c\u66f8\u304d\u8fbc\u307e\u308c\u3066\u3044\u308b\u30de\u30b9\u3092\u898b\u308b\u3002\u305d\u308c\u3089\u306e\u30de\u30b9\u306b\u3064\u3044\u3066\u3001\u305d\u306e\u30de\u30b9\u306e\u5024\u3092\u5217\u306e\u7dcf\u548c\u304b\u3089\u5f15\u304f\u3002\u3053\u308c\u306b\u3088\u3063\u3066(\u5217C\u306e\u7dcf\u548c)\u3092(\u5217C\u306e\u7dcf\u548c)-(\u30de\u30b9R,C\u306b\u66f8\u3044\u3066\u3042\u308b\u6570\u5b57)\u306b\u3059\u308b\u3053\u3068\u304c\u51fa\u6765\u308b\u3002\u3042\u3068\u306f\u666e\u901a\u306b\u6700\u5927\u5024\u3092\u53d6\u3063\u3066\u884c\u306e\u7dcf\u548c\u3068\u5408\u308f\u305b\u308c\u3070\u3088\u3044\u3002<\/p>\n\n\n\n
\u5404\u884c\u306b\u3064\u3044\u3066\u5217\u3092\u898b\u308b\u305f\u3081\u306b$O(\\log N)$\u3001\u5404\u30de\u30b9\u306b\u3064\u3044\u3066\u30bb\u30b0\u6728\u306e\u66f4\u65b0\u51e6\u7406\u304c\u8d70\u308b\u306e\u3067$O(N\\log N)$\u3001\u5168\u4f53\u3067$O(N\\log N)$\u3068\u306a\u308b\u3002<\/p>\n\n\n\n
G: \u89e3\u3051\u305a\u3002H,W\u304c\u5c0f\u3055\u3044\u306e\u3067\u305d\u3053\u304c\u72d9\u3044\u76ee\u306a\u306e\u3060\u308d\u3046\u304c\u3001\u30c8\u30ea\u30c3\u30ad\u30fc\u306a\u51fa\u984c\u3059\u304e\u3066\u624b\u306e\u3064\u3051\u3088\u3046\u304c\u306a\u304b\u3063\u305f\u3002<\/p>\n\n\n\n
GCJ Farewell Round\u306b\u51fa\u305f\u3002Atcoder\u3068\u51fa\u984c\u50be\u5411\u304c\u3061\u3087\u3063\u3068\u9055\u3063\u3066\u9762\u767d\u304b\u3063\u305f\u3002<\/p>\n\n\n\n
\u82f1\u8a9e\u306e\u8aad\u89e3\u3084\u51fa\u529b\u5f62\u5f0f\u306e\u90e8\u5206\u306a\u3069\u3067\u6642\u9593\u3092\u98df\u3063\u3066\u3057\u307e\u3063\u305f\u305f\u3081\u3001\u5f62\u5f0f\u306b\u6163\u308c\u3066\u3044\u308c\u3070\u3082\u3046\u5c11\u3057\u884c\u3051\u305f\u304b\u3082\u3057\u308c\u306a\u3044\u3002\u307e\u3042\u3067\u3082\u697d\u3057\u304b\u3063\u305f\u306e\u3067\u30e8\u30b7\uff01<\/p>\n\n\n\n
Round A<\/p>\n\n\n\n
1\u554f\u76ee: \u3084\u308b\u3060\u3051<\/p>\n\n\n\n
2\u554f\u76ee: \u7aef\u304b\u3089\u898b\u3066\u884c\u304d\u3001\u4eca\u307e\u3067\u7167\u3089\u3057\u305f\u533a\u9593\u306b\u3088\u3063\u3066\u7167\u3089\u3055\u308c\u306a\u3044\u96fb\u706f\u304c\u51fa\u3066\u304d\u305f\u3089\u305d\u306e1\u3064\u524d\u3092\u8ee2\u5012\u3055\u305b\u308b\u3002\u305d\u3082\u305d\u3082\u7167\u3089\u305b\u306a\u3044\u3088\u3046\u306a\u5834\u5408\u306f\u3001\u6700\u521d\u306b\u7aef\u3068\u5404\u96fb\u706f\u9593\u306e\u8ddd\u96e2\u3060\u3051\u898b\u3066\u304a\u3051\u3070\u5224\u5b9a\u3067\u304d\u308b\u3002<\/p>\n\n\n\n
3\u554f\u76ee: \u540c\u3058\u8272\u306e\u30ab\u30fc\u30c9\u304c2\u304b\u6240\u4ee5\u4e0a\u306b\u5206\u304b\u308c\u3066\u3044\u308b\u7b87\u6240\u304c\u3042\u308b\u3068\u5358\u8abf\u975e\u6e1b\u5c11\u5217\u306f\u4f5c\u308c\u306a\u3044\u306e\u3067\u4e0d\u53ef\u80fd\u3002\u305d\u3046\u3067\u306a\u3044\u306a\u3089\u3001\u7aef\u304b\u3089\u898b\u3066\u884c\u3063\u3066\u65b0\u3057\u3044\u8272\u304c\u51fa\u308b\u305f\u3073\u306b\u305d\u308c\u3092\u51fa\u305b\u3070\u3088\u3044\u3002<\/p>\n\n\n\n
4\u554f\u76ee: 26\u3092\u5f15\u304f\u300126*2\u3092\u5f15\u304f\u300126*3\u3092\u5f15\u304f…\u3068\u3084\u3063\u3066\u3044\u3063\u3066\u5f15\u3051\u306a\u3044\u3053\u3068\u304c\u5206\u304b\u3063\u305f\u3089\u305d\u3053\u3067\u6587\u5b57\u3092\u5224\u5b9a\u3059\u308b\u3060\u3051\u3002<\/p>\n\n\n\n
5\u554f\u76ee: \u30e9\u30f3\u30ec\u30f3\u30b0\u30b9\u5727\u7e2e\u3057\u3066\u3057\u307e\u3046\u3068\u697d\u3002\u540c\u3058\u624b\u306e\u4eba\u306e\u533a\u9593\u306ffloor(\u533a\u9593\u306e\u4eba\u6570\/2)\u3092\u66f8\u304d\u63db\u3048\u308c\u3070\u3088\u304f\u3001\u3053\u308c\u3092\u5404\u533a\u9593\u306b\u3064\u3044\u3066\u5408\u7b97\u3059\u308c\u3070\u3088\u3044\u3002\u5186\u5468\u306a\u306e\u3067\u3001\u6700\u521d\u306e\u4eba\u3068\u6700\u5f8c\u306e\u4eba\u304c\u540c\u3058\u624b\u306e\u5834\u5408\u306b\u6ce8\u610f\u3002\u305d\u308c\u304b\u3089\u5168\u54e1\u304c\u540c\u3058\u624b\u3092\u51fa\u3057\u3066\u3044\u308b\u5834\u5408\u3001\u3053\u308c\u306ffloor(\u4eba\u6570\/2)\u3067\u306f\u306a\u304fceil(\u4eba\u6570\/2)\u3068\u3059\u308b\u3002<\/p>\n\n\n\n
Round B<\/p>\n\n\n\n
1\u554f\u76ee: \u9b3c\u30c8\u30ec\u306e\u9663\u53d6\u5bfe\u5c40\u306b\u4f3c\u3066\u3044\u308b\u3002\u3053\u308c\u306f1\u6b21\u5143\u4e0a\u306a\u306e\u3067\u3001\u56de\u308a\u8fbc\u307e\u308c\u308b\u5fc3\u914d\u304c\u306a\u3044\u3002\u51fa\u6765\u308b\u9650\u308a\u76f8\u624b\u3092\u5f97\u70b9\u304c\u5c11\u306a\u3044\u5074\u306b\u62bc\u3057\u8fbc\u3081\u3066\u3084\u308b\u306e\u304c\u6700\u9069\u3068\u306a\u308b\u3002<\/p>\n\n\n\n
\u30a2\u30ea\u30b9\u306e\u521d\u671f\u4f4d\u7f6e\u3092\u6c7a\u3081\u305f\u5834\u5408\u3001\u30dc\u30d6\u306e\u6700\u9069\u306a\u521d\u671f\u4f4d\u7f6e\u306f\u30a2\u30ea\u30b9\u306e\u96a3\u3002\u96a3\u306b\u5c45\u3089\u308c\u306a\u3044\u5834\u5408\u306f\u51fa\u6765\u308b\u3060\u3051\u30a2\u30ea\u30b9\u306b\u8fd1\u3044\u4f4d\u7f6e\u3002\u3042\u3068\u306f\u30a2\u30ea\u30b9\u3068\u30dc\u30d6\u304c\u4e92\u3044\u306b\u8fd1\u3065\u304d\u3001\u3076\u3064\u304b\u3063\u305f\u3089\u3042\u3068\u306f\u5404\u81ea\u53d6\u308c\u308b\u30b1\u30fc\u30ad\u3092\u53d6\u3063\u3066\u3044\u304f\u306e\u304c\u6700\u5584\u3068\u306a\u308b\u3002<\/p>\n\n\n\n
\u30a2\u30ea\u30b9\u306e\u521d\u671f\u4f4d\u7f6e\u3092\u6c7a\u3081\u308c\u3070\u3042\u3068\u306e\u5f97\u70b9\u306f\u5168\u3066\u7c21\u5358\u306b\u6c7a\u307e\u308b\u306e\u3067\u3001\u30a2\u30ea\u30b9\u306e\u4f4d\u7f6e\u306f\u5168\u63a2\u7d22\u3057\u305f\u3002\u5168\u63a2\u7d22\u3067\u9593\u306b\u5408\u3046\u3068\u304d\u306f\u5168\u63a2\u7d22\u3059\u308b\u306e\u304c\u78ba\u5b9f\u3002<\/p>\n\n\n\n
2\u554f\u76ee: $kD = X_i-X_{N-i+1} mod N$\u3068\u306a\u308b\u3088\u3046\u306a\u7d76\u5bfe\u5024\u6700\u5c0f\u306ek\u3092$1\\leq i \\leq \\lfloor\\frac{N}{2}\\rfloor$\u306b\u3064\u3044\u3066\u63a2\u3057\u3066\u7d76\u5bfe\u5024\u306e\u7dcf\u548c\u3092\u53d6\u308b\u3002\u62e1\u5f35\u30e6\u30fc\u30af\u30ea\u30c3\u30c9\u3067\u9811\u5f35\u3063\u3066\u4e00\u6b21\u4e0d\u5b9a\u65b9\u7a0b\u5f0f\u3092\u89e3\u3051\u3070\u3088\u308d\u3057\u3044\u3002\u30e9\u30a4\u30d6\u30e9\u30ea\u6574\u5099\u3057\u3066\u3066\u3088\u304b\u3063\u305f\u3002\u306a\u304a\u7d76\u5bfe\u5024\u306a\u306e\u306f\u3001k<0\u304c\u9006\u56de\u8ee2\u306b\u5bfe\u5fdc\u3057\u3066\u3044\u308b\u305f\u3081\u3002<\/p>\n\n\n\n
3\u554f\u76ee: \u300c\u3042\u308b\u6570\u5b57\u3092\u63a1\u7528\u3057\u305f\u4e0a\u3067\u3001\u305d\u306e\u6570\u5b57\u4ee5\u4e0a(\u4ee5\u4e0b)\u306e\u756a\u53f7\u306e\u307f\u3067\u4f5c\u308c\u308b\u6700\u5927\u306espaciout\u306aset\u300d\u3092DP\u3067\u6c42\u3081\u308b\u3002\u6c42\u307e\u3063\u305f\u3089\u3042\u3068\u306f\u5404\u6570\u5b57\u306b\u3064\u3044\u3066\u3001\u305d\u306e\u6570\u5b57\u4ee5\u4e0a\u306e\uff5e\u3068\u305d\u306e\u6570\u5b57\u4ee5\u4e0b\u306e\uff5e\u3092\u8db3\u3057\u30661\u3092\u5f15\u3051\u3070\u3088\u3044\u3002<\/p>\n\n\n\n
4\u554f\u76ee: \u5168\u304f\u5206\u304b\u3089\u305a\u3002UnionFind\u4f7f\u3063\u305f\u611a\u76f4\u89e3\u306f\u3055\u3059\u304c\u306b\u66f8\u3051\u305f\u306e\u3067\u90e8\u5206\u70b9\u306f\u51fa\u305f\u304c\u3002<\/p>\n\n\n\n
5\u554f\u76ee: \u3082\u3046\u3061\u3087\u3044\u3067\u89e3\u3051\u305d\u3046\u3060\u3063\u305f\u306e\u3060\u304c\u7121\u7406\u3060\u3063\u305f\u3002\u307e\u305a\u3001Functional Graph\u3067\u3042\u308b\u3053\u3068\u304c\u5206\u304b\u308b\u3002\u6728\u306e\u672b\u7aef\u90e8\u306f\u4f7f\u3044\u307e\u308f\u305b\u308b\u3082\u306e\u304c\u6765\u308b\u306f\u305a\u304c\u306a\u3044\u306e\u3067\u3001\u307e\u305a\u306f\u7aef\u304b\u3089\u3084\u3063\u3066\u3044\u3051\u3070\u3088\u3044\u3002\u3042\u3068\u306f\u6728\u306a\u306e\u3067\u8ff7\u3046\u3053\u3068\u304c\u306a\u304f\u3001\u30b5\u30a4\u30af\u30eb\u90e8\u306b\u5230\u9054\u3059\u308b\u3002\u3053\u3053\u304b\u3089\u306e\u51e6\u7f6e\u304c\u5206\u304b\u3089\u306a\u304b\u3063\u305f\u3068\u3044\u3046\u304b\u3001\u81ea\u4fe1\u304c\u6301\u3066\u306a\u304b\u3063\u305f\u3002\u3042\u3068\u3001\u30b0\u30e9\u30d5\u304c\u9023\u7d50\u306a\u3069\u3068\u3044\u3046\u4fdd\u8a3c\u306f\u3069\u3053\u306b\u3082\u306a\u3044\u306e\u3067\u975e\u9023\u7d50\u306e\u5834\u5408\u3082\u5bfe\u5fdc\u3059\u308b\u5fc5\u8981\u304c\u3042\u308b\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u30b5\u30a4\u30c8\u79fb\u884c\u306e\u305f\u3081\u306e\u6e96\u5099\u3092\u771f\u9762\u76ee\u306b\u9032\u3081\u305f\u3002Vulkan\u5165\u9580\u3092\u3082\u3046\u3061\u3087\u3063\u3068\u66f8\u304d\u9032\u3081\u3066\u304b\u3089\u3068\u304b\u8a00\u3063\u3066\u3044\u305f\u304c\u3001\u3069\u3046\u8003\u3048\u3066\u3082\u305d\u3093\u306a\u306e\u5f85\u3063\u3066\u305f\u3089\u3044\u304f\u3089\u3067\u3082\u6642\u9593\u304c\u7d4c\u3064\u3057\u3001\u65e9\u304f\u51fa\u3059\u3079\u304d\u3002 ABC298\u306b\u51fa\u305f\u3002\u304b\u306a\u308a\u5931\u6557\u3057\u305f\u3002E\u304c\u89e3\u3051\u306a\u304b … <\/p>\n