AtCoder Grand Contest 028 C 「Min Cost Cycle」

問題文

C - Min Cost Cycle

 

min(x,y)はxとyの好きな方をとるとしても結果は同じ、みたいなアイディアは何回か見たことがあった。

 

x1,x2,...,xNを1,2,...,Nの順列として、x1→x2→...→xN→x1というサイクルを作ると、このときのコストはmin(A[x1],B[x2])+min(A[x2],B[x3])+...+min(A[xN],B[x1])となる。しかし、min(x,y)はxとyの好きな方を取れるとしてもコストの最小値はかわらない(結局、小さい方を取るのが最適なので)ので、そのように制約を緩められる。

さて、そうすると各頂点を「AもBも採用する」「Aだけ採用する」「Bだけ採用する」「AもBも採用しない」という4パターンにわけることができる。

ここで「AもBも採用する」頂点と「AもBも採用しない」頂点は同数でないといけないことがわかる(N個の頂点からN個の値を採用するので)。

そこで場合分けをしよう。

ケース1: 「AもBも採用する」頂点が0個のとき

この場合、全頂点が「Aだけ採用する」になるか、全頂点が「Bだけ採用する」になるかのどちらか。いずれも簡単にコストを計算できる。

ケース2: 「AもBも採用する」頂点が1個以上のとき

なるべく小さい方から採用していきたいので長さ2Nの数列A[1],A[2],...,A[N],B[1],B[2],...,B[N]をソートしておく。

このとき先頭からN番目までにAもBも含まれるような頂点が存在したとすると、先頭からN番目までの値を全て採用できる。

(理由)

このような頂点vが存在するとき、「Aだけ採用する」頂点(〇→という形)を→v→の右に、「Bだけ採用する」頂点(→〇という形)を左につなげていけば→〇→...→v→〇→...→〇→という形になり、「AもBも採用しない」頂点(〇という形)を挟めばサイクルが出来るから。

 

 

もしこのような頂点が存在しなかったら、「AもBも採用する」頂点をどれにするかN通り試してやる(先頭からN番目までにAかBが含まれているので、それをのぞいてN+1番目かN+2番目の値を採用すればいい)。