codeFlyer (bitFlyer Programming Contest)

Submission #2603957

Source codeソースコード

N,D = map(int,input().split(" "))
X = list(map(int,input().split(" ")))

far_D = [0]*N
acc = [0]*N

#各都市に対する(右にD以上離れている都市数)を計算
for i in range(N):
	#二分探索
	lb = i
	ub = (N-1)
	bound = (N-1)
	while lb <= ub:
		mid = (lb + ub) //2
		if X[mid] - X[i] <= D:
			lb = mid + 1
			bound = mid
		else:
			ub = mid - 1

	#X_boundはギリギリD以内
	far_D[i] = (N - 1 - bound) #Dより離れてる数

	#累積和
	if i != 0:
		acc[i] = acc[i-1] + far_D[i]
	else:
		acc[0] = far_D[0]

pattern = 0
for i in range(N):
	# 1
	if far_D[i] >= 2:
		pattern += (far_D[i] * (far_D[i]-1) // 2)
	# 2
	bound = (N - 1 - far_D[i]) #ギリギリD以内
	pattern += (acc[bound] - acc[i])

	# 3
	if bound - i >= 2:
		pattern += ((bound-i)*(bound-i-1)//2)

total = (N*(N-1)*(N-2)//6)
print(total - pattern)

Submission

Task問題 C - 徒歩圏内
User nameユーザ名 banboooo044
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 400
Source lengthソースコード長 876 Byte
File nameファイル名
Exec time実行時間 938 ms
Memory usageメモリ使用量 15940 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt
All 400 / 400 01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01.txt AC 938 ms 15392 KB
02.txt AC 795 ms 15520 KB
03.txt AC 938 ms 14480 KB
04.txt AC 868 ms 15568 KB
05.txt AC 915 ms 15940 KB
06.txt AC 879 ms 14228 KB
07.txt AC 850 ms 15828 KB
08.txt AC 757 ms 14348 KB
09.txt AC 17 ms 3064 KB
10.txt AC 917 ms 14736 KB
11.txt AC 913 ms 15732 KB
12.txt AC 828 ms 15500 KB
sample-01.txt AC 17 ms 3064 KB
sample-02.txt AC 17 ms 3064 KB
sample-03.txt AC 17 ms 3064 KB
sample-04.txt AC 17 ms 3064 KB