\u4eca\u65e5\u89e3\u3044\u305f\u7af6\u30d7\u30ed\u306e\u554f\u984c\u3002<\/p>\n\n\n\n
ARC151-B: \u6570\u5217A\u304c\u6570\u5217B\u3088\u308a\u8f9e\u66f8\u9806\u3067\u5c0f\u3055\u3044\u3068\u3044\u3046\u3053\u3068\u306f\u3001\u3042\u308bi\u304c\u3042\u3063\u3066\u3001$1\\leq k < i$\u306b\u304a\u3044\u3066$A_k=B_k$\u3067\u3042\u308a$A_i<B_i$\u3067\u3042\u308b\u3068\u3044\u3046\u3053\u3068\u3067\u3042\u308b\u3002\u3064\u307e\u308a\u3053\u306ei\u304c\u3069\u3053\u304b\u306b\u3088\u3063\u3066N\u901a\u308a\u306e\u5834\u5408\u304c\u3042\u308b\u3002\u3053\u306e\u554f\u984c\u3067\u306f$A_1<A_{P_1}$\u306e\u5834\u5408\u3001$A_2<A_{P_2}$\u306e\u5834\u5408…\u3068\u8003\u3048\u3066\u3044\u3051\u3070\u3088\u3044\u3002<\/p>\n\n\n\n
$A_1<A_{P_1}$\u306e\u3068\u304d\u3001$P_1=1$\u306a\u3089\u3070\u5b9f\u73fe\u4e0d\u53ef\u80fd\u3002\u305d\u3046\u3067\u306a\u3051\u308c\u3070$A_1$\u3068$A_{P_1}$\u306e\u9078\u3073\u65b9\u306f$_MC_2$\u901a\u308a\u3042\u308b\u3002\u6b8b\u308a\u306e$N-2$\u8981\u7d20\u306f\u4efb\u610f\u306b\u3068\u308c\u308b\u306e\u3067$M^{N-2}$\u901a\u308a\u3042\u308b\u3002<\/p>\n\n\n\n
$A_1=A_{P_1}$\u304b\u3064$A_2<A_{P_2}$\u306e\u3068\u304d\u3001$P_2=2$\u306a\u3089\u3070\u5b9f\u73fe\u4e0d\u53ef\u80fd\u3002\u307e\u305f$P_1=2, P_2=1$\u306e\u3088\u3046\u306a\u5834\u5408\u3001$A_2=A_{P_2}$\u3068\u3044\u3046\u3053\u3068\u306b\u306a\u3063\u3066\u3057\u307e\u3046\u306e\u3067\u5b9f\u73fe\u4e0d\u53ef\u80fd\u306b\u306a\u308b\u3002\u305d\u3046\u3067\u306a\u3051\u308c\u3070\u3084\u306f\u308a$A_2$\u3068$A_{P_2}$\u306e\u9078\u3073\u65b9\u306f$_MC_2$\u901a\u308a\u3042\u308a\u3001\u6b8b\u308a\u306e\u7e1b\u3089\u308c\u3066\u3044\u306a\u3044\u8981\u7d20\u306f\u4efb\u610f\u306b\u3068\u308c\u308b\u3002$A_1=A_{P_1}$\u304c\u3042\u308b\u306e\u3060\u3051\u81ea\u7531\u5ea6\u306f\u4f59\u5206\u306b\u6e1b\u308b\u3053\u3068\u306b\u6ce8\u610f\u3002<\/p>\n\n\n\n
\u8981\u3059\u308b\u306bN\u901a\u308a\u306e\u5404\u5834\u5408\u306b\u3064\u3044\u3066\u3001\u5b9f\u73fe\u53ef\u80fd\u304b\u3069\u3046\u304b\uff0b\u7e1b\u3089\u308c\u3066\u3044\u306a\u3044\u8981\u7d20\u306f\u3044\u304f\u3064\u3042\u308b\u304b(\u81ea\u7531\u5ea6\u304c\u3044\u304f\u3064\u3042\u308b\u304b)\u3092\u8a08\u7b97\u3067\u304d\u308c\u3070\u3088\u3044\u3002\u540c\u5024\u95a2\u4fc2\u3092\u7ba1\u7406\u3057\u305f\u3044\u3068\u306a\u3063\u305f\u3089\u3053\u308c\u306fUnionFind\u3067\u3042\u308b\u3002<\/p>\n\n\n\n
$A_k=A_{P_k}\\ (k<i)$\u3001$A_i<A_{P_i}$\u306e\u30d1\u30bf\u30fc\u30f3\u6570\u3092\u8abf\u3079\u308b\u306b\u306f\u3001\u307e\u305ai-1\u500b\u306e\u30a4\u30b3\u30fc\u30eb\u306b\u3064\u3044\u3066UnionFind\u3067\u7e4b\u3052\u305f\u3046\u3048\u3067\u3001$i$\u3068$P_i$\u304c\u30a4\u30b3\u30fc\u30eb\u3067\u7d50\u3070\u308c\u3066\u3044\u308b\u304b\u5224\u65ad\u3057\u3066\u5b9f\u73fe\u53ef\u80fd\u6027\u3092\u8abf\u3079\u308b\u3002\u6b21\u306b\u9023\u7d50\u6210\u5206\u306e\u6570\u3092\u6570\u3048\u3001$_MC_2\\times M^{\u9023\u7d50\u6210\u5206\u6570-2}$\u3092\u8a08\u7b97\u3059\u308c\u3070\u3088\u3044\u3002<\/p>\n\n\n\n
\u3053\u306e\u8a08\u7b97\u306f\u9806\u306b$i$\u3092\u5897\u3084\u3057\u3066\u3044\u3051\u3070\u524d\u56de\u306e\u7d50\u679c\u304c\u4f7f\u3048\u308b\u3002\u4e8c\u5206\u7d2f\u4e57\u3067\u3079\u304d\u4e57\u3092\u8a08\u7b97\u3059\u308b\u3068\u304d\u306elog\u304c\u30dc\u30c8\u30eb\u30cd\u30c3\u30af\u306b\u306a\u308a\u3001\u5168\u4f53$O(N\\log N)$\u3002\u5b9f\u969b\u306b\u306f\u9023\u7d50\u6210\u5206\u6570\u306f\u3069\u3093\u3069\u3093\u6e1b\u3063\u3066\u3044\u304f\u306f\u305a\u306a\u306e\u3067\u3001\u53b3\u5bc6\u306b\u898b\u7a4d\u3082\u308c\u3070\u3055\u3089\u306b\u901f\u3044\u304b\u3082\u3057\u308c\u306a\u3044\u3002<\/p>\n\n\n\n
\u4eca\u9031\u306e\u80ce\u754c\u4e3b\u3092\u8aad\u3093\u3060\u3002\u30b5\u30bf\u30ca\u30ad\u30a2\u3001\u304a\u524d\u305d\u308c\u660e\u3089\u304b\u306b\u7834\u6ec5\u306e\u6d41\u308c\u3067\u306f\uff1f\uff1f\uff1f\uff1f\u305b\u3081\u3066\u3053\u3046\u3001\u300c\u5927\u60e8\u4e8b\u304c\u8d77\u3053\u3089\u306a\u3044\u65b9\u306b\u8ced\u3051\u308b\u300d\u3068\u304b\u306a\u3089\u5206\u304b\u308b\u3051\u3069\u3055\u3042\u3002\u65e5\u5948\u5b50\u3092\u3082\u3046\u3053\u308c\u4ee5\u4e0a\u30af\u30bd\u307f\u305f\u3044\u306a\u76ee\u306b\u906d\u308f\u305b\u306a\u3044\u3067\u304f\u308c\u3002<\/p>\n\n\n\n
\u30b5\u30bf\u30ca\u30ad\u30a2\u306e\u7b56\u306f\u4e88\u60f3\u901a\u308a\u4f55\u304b\u3057\u3089\u306e\u795e\u7363\u306e\u53ec\u559a\u3060\u3063\u305f\u3088\u3046\u3060\u3002\u30a2\u30d0\u30c9\u30f3\u3066\u3044\u3046\u306e\u306f\u3069\u3053\u306e\u4f55\u306e\u3069\u3046\u3044\u3046\u795e\u7363\u3060\u308d\u3046\u304b\u3002\u308d\u304f\u306a\u3053\u3068\u304c\u8d77\u3053\u308a\u305d\u3046\u306b\u306a\u3044\u304c\u3002<\/p>\n\n\n\n
Wikipedia\u60c5\u5831\u3060\u3068\u30e8\u30cf\u30cd\u306e\u9ed9\u793a\u9332\u306b\u767b\u5834\u3059\u308b\u5948\u843d\u306e\u738b\u3067\u3042\u308a\u3001\u300c\u7834\u58ca\u8005\u300d\u3068\u3044\u3063\u305f\u610f\u5473\u306e\u540d\u524d\u3089\u3057\u3044\u3002\u58ca\u3059\u529b\u306e\u53f8\u795e\u306e\u795e\u7363\u306a\u306e\u3060\u308d\u3046\u304b\u3002\u5168\u304f\u95a2\u4fc2\u306a\u3044\u304c\u300c\u8150\u6d77\u306b\u7720\u308b\u738b\u5973\u306e\u30a2\u30d0\u30c9\u30fc\u30f3\u300d\u3068\u3044\u3046\u30b2\u30fc\u30e0\u304cbiim\u5144\u8cb4\u306b\u30d7\u30ec\u30a4\u3055\u308c\u3066\u3044\u305f\u306a\u3002<\/p>\n\n\n\n
PICO4\u304c\u65e9\u901f\u5c4a\u3044\u305f\u3002\u3068\u308a\u3042\u3048\u305a\u958b\u5c01\u3057\u3066\u4e2d\u8eab\u3068\u88c5\u7740\u611f\u306a\u3069\u3092\u78ba\u304b\u3081\u305f\u3002<\/p>\n\n\n\n
Valve Index\u306b\u6bd4\u3079\u308b\u3068\u3001\u5f8c\u982d\u90e8\u306b\u5f53\u305f\u308b\u90e8\u5206\u304c\u3061\u3087\u3063\u3068\u786c\u3044\u3002\u30b4\u30e0\u306b\u76ae\u3092\u304b\u3076\u305b\u3066\u3042\u308b\u611f\u3058\u306a\u306e\u3067\u30af\u30c3\u30b7\u30e7\u30f3\u6027\u306f\u3042\u307e\u308a\u9ad8\u304f\u306a\u3044\u6a21\u69d8\u3060\u3002\u305d\u306e\u307b\u304b\u306f\u3042\u307e\u308a\u6c17\u306b\u306a\u308b\u70b9\u306f\u306a\u3044\u3002\u8efd\u3044\u3068\u3044\u3048\u3070\u8efd\u3044\u304b\u3082\u3057\u308c\u306a\u3044\u3002<\/p>\n\n\n\n
\u30b3\u30f3\u30c8\u30ed\u30fc\u30e9\u306f\u89aa\u6307\u62bc\u3057\u30dc\u30bf\u30f34\u3064+\u30b9\u30c6\u30a3\u30c3\u30af1\u3064+\u4eba\u5dee\u3057\u6307\u3068\u4e2d\u6307\u305d\u308c\u305e\u308c\u306b\u30dc\u30bf\u30f3\u304c1\u3064\u3065\u3064\u3068\u3044\u3063\u305f\u5f62\u3060\u3002Index\u30b3\u30f3\u3068\u3061\u304c\u3063\u3066\u3001\u4eba\u5dee\u3057\u6307\u3067\u62bc\u305b\u308b\u30ad\u30fc\u306f\u300c\u30ab\u30c1\u30c3\u300d\u3068\u306f\u8a00\u308f\u306a\u3044\u3002\u8f2a\u3063\u304b\u306b\u306a\u3063\u3066\u3044\u308b\u90e8\u5206\u306e\u5b58\u5728\u610f\u7fa9\u306f\u5168\u304f\u308f\u304b\u3089\u306a\u3044\u3002<\/p>\n\n\n\n
\u4eca\u65e5\u306f\u3082\u3046\u9045\u3044\u306e\u3067\u660e\u65e5\u672c\u683c\u7684\u306b\u3044\u3058\u308b\u3002<\/p>\n\n\n\n
\u7b4b\u30c8\u30ec\u3092\u3057\u305f\u3002\u4eca\u65e5\u306f\u30b9\u30af\u30ef\u30c3\u30c8\u3002\u307e\u305f\u9593\u304c\u7a7a\u3044\u3066\u3057\u307e\u3063\u305f\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4eca\u65e5\u89e3\u3044\u305f\u7af6\u30d7\u30ed\u306e\u554f\u984c\u3002 ARC151-B: \u6570\u5217A\u304c\u6570\u5217B\u3088\u308a\u8f9e\u66f8\u9806\u3067\u5c0f\u3055\u3044\u3068\u3044\u3046\u3053\u3068\u306f\u3001\u3042\u308bi\u304c\u3042\u3063\u3066\u3001$1\\leq k < i$\u306b\u304a\u3044\u3066$A_k=B_k$\u3067\u3042\u308a$A_i<B_i$\u3067\u3042\u308b\u3068\u3044\u3046\u3053\u3068\u3067\u3042\u308b\u3002 … <\/p>\n