提出 #32497250

ソースコード 拡げる

(N,M),*TC = $<.map{|ln| ln.split.map(&:to_i) }
E = [*0...N+M].combination(2).map{|i,j|
	x0,y0,r0 = TC[i]
	x1,y1,r1 = TC[j]
	d = Math.hypot(x1-x0,y1-y0).round 12
	d = if ! r0 && ! r1 then d
		elsif r0 && ! r1 then (d-r0).abs
		elsif ! r0 && r1 then (d-r1).abs
		elsif r0+r1<d then d-r0-r1
		elsif d<(r1-r0).abs then (r1-r0).abs-d
		else 0
	end
	next i,j,d
}.sort_by{_3}
F = lambda{|g,i|
	g[i]<0 ? i : g[i] = F[g,g[i]]
}
U = lambda{|g,i,j,d|
	i,j = F[g,i],F[g,j]
	next 0 if i==j
	i,j = j,i if g[j]<g[i]
	g[i] += g[j]
	g[j] = i
	next d
}

p (1<<M).times.map{|c|
	tc = (c+1<<N)-1
	g = [-1]*(N+M)
	next E.sum{|i,j,d|
		tc[i]+tc[j]<2 ? 0 : U[g,i,j,d]
	}#.tap{warn'%0*b %.1f'%[N+M,tc,_1]}
}.min

提出情報

提出日時
問題 L - 都市計画
ユーザ ds14050
言語 Ruby (2.7.1)
得点 6
コード長 721 Byte
結果 AC
実行時間 176 ms
メモリ 14656 KiB

コンパイルエラー

./Main.rb:12: warning: mismatched indentations at 'end' with 'else' at 11

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 6 / 6
結果
AC × 3
AC × 28
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All large_answer_00.txt, manual_00.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, sample_01.txt, sample_02.txt, sample_03.txt, surrounding_00.txt, surrounding_01.txt, use_all_00.txt
ケース名 結果 実行時間 メモリ
large_answer_00.txt AC 60 ms 14480 KiB
manual_00.txt AC 58 ms 14396 KiB
random_00.txt AC 58 ms 14448 KiB
random_01.txt AC 57 ms 14492 KiB
random_02.txt AC 60 ms 14572 KiB
random_03.txt AC 62 ms 14468 KiB
random_04.txt AC 173 ms 14648 KiB
random_05.txt AC 171 ms 14640 KiB
random_06.txt AC 176 ms 14620 KiB
random_07.txt AC 174 ms 14476 KiB
random_08.txt AC 175 ms 14488 KiB
random_09.txt AC 173 ms 14572 KiB
random_10.txt AC 173 ms 14636 KiB
random_11.txt AC 173 ms 14488 KiB
random_12.txt AC 56 ms 14452 KiB
random_13.txt AC 81 ms 14588 KiB
random_14.txt AC 88 ms 14568 KiB
random_15.txt AC 56 ms 14448 KiB
random_16.txt AC 55 ms 14496 KiB
random_17.txt AC 56 ms 14508 KiB
random_18.txt AC 113 ms 14636 KiB
random_19.txt AC 64 ms 14388 KiB
sample_01.txt AC 61 ms 14444 KiB
sample_02.txt AC 58 ms 14540 KiB
sample_03.txt AC 59 ms 14564 KiB
surrounding_00.txt AC 175 ms 14604 KiB
surrounding_01.txt AC 176 ms 14656 KiB
use_all_00.txt AC 61 ms 14592 KiB