解題報告 2021/07/14

A. Balanced Team

https://codeforces.com/group/n75uQpTCBs/contest/325340/problem/A
status: done

Problem Analysis

List S is a sublist of the input list a . Find the maximum length of list S while S.max() - S.min() <= 5.

Source Code

n = int(input())
students = list( map(int, input().split()) )
students.sort()
max_stu = 0

if students[-1] == students[0]:
	print( len(students) )

else:
	for start in range(n):
		temp = 0
		end = start
		while (end < n) and (students[end] - students[start] < 6):
			temp += 1
			end += 1
		
		if (temp > max_stu):
			max_stu = temp
			if max_stu == n: break
		
	print(max_stu)

Verdict Message

TLE on test 18

Corrected Source Code

n = int(input())
students = list( map(int, input().split()) )
students.sort()
max_stu = 0
end = 0

for start in range(n):
    while (end < n) and (students[end] - students[start] < 6):
        end+=1
    
    temp = end - start
    
    if temp > max_stu :
        max_stu = temp
        if max_stu ==n:
        break
        
print(max_stu)

Each round, end will increase from the former end, thus passing over unnecessary runs.
ex.
Let's say when start = 1, end = 6. When the code proceeds to start = 2, end = 1 ~ 6 is surplus.

Verdict Message

AC

B. Number of Ways

https://codeforces.com/group/n75uQpTCBs/contest/325340/problem/B

status: done

Problem Analysis

total / 3
2 * total / 3
[1] [2] [3]
sum([1]) = total / 3
sum([2]) + sum([1]) = 2 * total / 3

Eevee's Source Code

N = int(input())
A = list( map(int, input().split()) )
total = sum(A)    # only calculate sum(A) once to reduce complexity

if total % 3 != 0:
    print('0')
    exit(0)


first_cut_num = 0
p_num = 0
ans = 0

for i in range(N-1):
    p_sum += A[i]
    if i > 0 and p_sum == total * 2 // 3:
        ans += first_cut_num
    
    if p_sum == total // 3:
         first_cut_num += 1
         
print(ans)

Verdict Message

AC

A. Queue

https://codeforces.com/group/n75uQpTCBs/contest/326285/problem/A
status: undone

Problem Analysis

• If N is even: just start from head and end from tail
• If N is odd: get all even elements first, then find who is the first
  • The number that only appeared once in heading is the first

Source Code

n = int(input())
students = []
queue_a = []
queue_b = []

for i in range(n):
	stu = list( map(int, input().split()) )
	if stu[0] == 0:
		queue_a.append(stu)

	else:
		students.append(stu)


for stu in students:
	if stu[0] == queue_a[-1][1]:
		queue_a.append(stu)
		students.pop(stu)

for stu in students:
# undone

Eevee's Source Code

N = int(input())
ans = [-1] * N

head = [-1] * (1<<20)
tail = [-1] * (1<<20)

for _ in range(N):
  h, t = map(int, input().split())
  tail[h] = t
  head[t] = h

if N % 2 == 0:
  st = 0
  idx = 1
  while tail[st] != -1:
    st = tail[st]
    ans[idx] = st
    idx += 2
  ed = 0
  idx = N - 2
  while head[ed] != -1:
    ed = head[ed]
    ans[idx] = ed
    idx -= 2
else:
  st = 0
  idx = 1
  while tail[st] != 0:
    st = tail[st]
    ans[idx] = st
    idx += 2
  st = [idx for idx, value in enumerate(head) if value == -1 and tail[idx] != -1][0]
  idx = 0
  while st != -1:
    ans[idx] = st
    st = tail[st]
    idx += 2
print(' '.join(map(str, ans)))    # join every element in the list 'ans' into a string then print out

Verdict Message

AC