提出 #48014051

ソースコード 拡げる

N,M,*C = $<.read.split.map(&:to_i)
SC = C[1..].inject([C[0]]){|s,c| s<<s[-1]+c }<<0
SL,SM = (N-1)/2,N/2+1
K0,K1 = [(N+1)/2,N/2+1].map{|m| SC.index{|s| m<=s } }
DK = (K1-K0)*0.5
M0,M1 = (K0+K1)*0.5,(K0+K1)*0.5+1
L0 = 1.0*(0...K0).sum{|k| k*C[k] }
L1 = L0+SC[K0-1]
R0 = 1.0*(K1+1...M).sum{|k| k*C[k] }
R1 = R0+N-SC[K1]
D = lambda{|m|
	l0,l1,r0,r1 = L0,L1,R0,R1
	[K0,K1].uniq[0,2-N%2].each{|k|
		s0,s = SC[k-1],SC[k]
		l0 += k*[[s,SL].min-s0,0].max
		l1 += [k+1,m-DK].min*[[s,SL].min-s0,0].max
		r0 += [k,m+DK].max*[s-[s0,SM].max,0].max
		r1 += (k+1)*[s-[s0,SM].max,0].max
	}
	l = (l0+r0+m*(2-N%2))/N
	r = (l1+r1+m*(2-N%2))/N
	next m<l ? l-m : r<m ? m-r : 0.0
}
D0,D1 = D[M0],D[M1]
m0,m3 = M0,M1
d0,d3 = D0,D1
100.times{
	m1 = (m0+m0+m3)/3
	m2 = (m0+m3+m3)/3
	d1 = D[m1]
	d2 = D[m2]
	if d1<d2
		m3,d3 = m2,d2
	else
		m0,d0 = m1,d1
	end
}

p [D0,D1,d0].min

提出情報

提出日時
問題 N - 度数分布
ユーザ ds14050
言語 Ruby (ruby 3.2.2)
得点 6
コード長 892 Byte
結果 AC
実行時間 195 ms
メモリ 33732 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 6 / 6
結果
AC × 3
AC × 58
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random2_01.txt, random2_02.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, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt, random_40.txt, random_41.txt, random_42.txt, random_43.txt, random_44.txt, random_45.txt, random_46.txt, random_47.txt, random_48.txt, random_49.txt, random_50.txt, random_51.txt, random_52.txt, random_53.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
random2_01.txt AC 195 ms 33332 KiB
random2_02.txt AC 105 ms 32708 KiB
random_01.txt AC 45 ms 17404 KiB
random_02.txt AC 45 ms 17420 KiB
random_03.txt AC 46 ms 17628 KiB
random_04.txt AC 46 ms 17500 KiB
random_05.txt AC 45 ms 17576 KiB
random_06.txt AC 45 ms 17484 KiB
random_07.txt AC 46 ms 17564 KiB
random_08.txt AC 46 ms 17424 KiB
random_09.txt AC 45 ms 17536 KiB
random_10.txt AC 45 ms 17428 KiB
random_11.txt AC 46 ms 17360 KiB
random_12.txt AC 46 ms 17408 KiB
random_13.txt AC 45 ms 17564 KiB
random_14.txt AC 46 ms 17444 KiB
random_15.txt AC 46 ms 17488 KiB
random_16.txt AC 45 ms 17388 KiB
random_17.txt AC 46 ms 17444 KiB
random_18.txt AC 45 ms 17536 KiB
random_19.txt AC 46 ms 17440 KiB
random_20.txt AC 45 ms 17460 KiB
random_21.txt AC 45 ms 17416 KiB
random_22.txt AC 45 ms 17632 KiB
random_23.txt AC 46 ms 17380 KiB
random_24.txt AC 46 ms 17504 KiB
random_25.txt AC 45 ms 17520 KiB
random_26.txt AC 46 ms 17440 KiB
random_27.txt AC 46 ms 17540 KiB
random_28.txt AC 45 ms 17376 KiB
random_29.txt AC 46 ms 17560 KiB
random_30.txt AC 47 ms 17388 KiB
random_31.txt AC 46 ms 17480 KiB
random_32.txt AC 101 ms 32596 KiB
random_33.txt AC 100 ms 32632 KiB
random_34.txt AC 101 ms 32956 KiB
random_35.txt AC 102 ms 32648 KiB
random_36.txt AC 101 ms 32756 KiB
random_37.txt AC 101 ms 33644 KiB
random_38.txt AC 102 ms 32728 KiB
random_39.txt AC 101 ms 32572 KiB
random_40.txt AC 101 ms 32724 KiB
random_41.txt AC 100 ms 32576 KiB
random_42.txt AC 102 ms 33328 KiB
random_43.txt AC 99 ms 33592 KiB
random_44.txt AC 102 ms 33732 KiB
random_45.txt AC 100 ms 32728 KiB
random_46.txt AC 102 ms 32532 KiB
random_47.txt AC 101 ms 32704 KiB
random_48.txt AC 101 ms 32572 KiB
random_49.txt AC 101 ms 32708 KiB
random_50.txt AC 99 ms 32700 KiB
random_51.txt AC 97 ms 32648 KiB
random_52.txt AC 101 ms 33656 KiB
random_53.txt AC 101 ms 33640 KiB
sample_01.txt AC 46 ms 17544 KiB
sample_02.txt AC 45 ms 17524 KiB
sample_03.txt AC 46 ms 17420 KiB