[PYTHON] Looking back on ABC155

This is my first post. Thank you. I will summarize the review of ABC155 that was done yesterday in practice.

A problem

Problem statement

For the number of triplets, when two are equal and the other one is different, the triplet is said to be "poor." Given the three integers A, B, and C, print Yes if the triplet is poor, or No otherwise.

Answer example

a = set(map(int, input().split()))
if len(a) == 2:
  print("Yes")
else:
  print("No")

You can judge whether it is poor or not by looking at the number of elements using the set set ().

B problem

Problem statement

You are an immigration officer in the Kingdom of AtCoder. Immigrant documents contain several integers, and your job is to determine if these meet the criteria. The terms and conditions require that entry be approved when and only when the following conditions are met: All integers on the document that are even are divisible by 3 or 5. When following the above rules, print APPROVED if you approve immigrants with N integers A1, A2,…, AN in the document, otherwise print DENIED.

Answer example

N = int(input())
A = list(map(int, input().split()))
flag = 0
for i in range(N):
  if A[i] % 2 == 0:
    if A[i] % 3 == 0 or A[i] % 5 == 0:
      pass
    else:
      flag = 1
      break
if flag == 0:
  print("APPROVED")
else:
  print("DENIED")

If there is an even number that is not divisible by 3 or 5, rewrite the flag and break it. Finally, output according to the value of flag.

C problem

There are N ballots, and the string $ S_i $ is written on the $ i \ (1 ≤ i ≤ N) $ sheet. Output all the character strings that have been written the most times in ascending order in dictionary order.

First, I created a dict and put a character in key and the number of occurrences in value. .. .. TLE. I had a feeling that there was only a flag that didn't work today.

Sample answer (TLE)

N = int(input())
dic = {}
for i in range(N):
  s = str(input())
  if not s in dic:
    dic[s] = 1
  else:
    dic[s] += 1
max_k_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]
max_k_list = sorted(max_k_list)
for i in max_k_list:
  print(i)

~~ The reason for TLE here is probably that the first for statement and the subsequent if not s in dic: are calculated to be close to $ O (N ^ 2) $. ~~ (If not, please comment) max_k_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())] It became $ O (N ^ 2) $ by getting the maximum value in the for statement every time. Since the maximum value does not change, you can eliminate unnecessary calculations by getting it outside the loop, and you can make it $ O (N) $. (I forgot that I changed this at the time of AC ...) ~~ Finally, it was a good idea to use the collections module. ~~

Answer example (AC)

import collections

N = int(input())
a = []
for i in range(N):
  a.append(str(input()))
a = collections.Counter(a)
b = max(a.values())
max_k_list = [kv[0] for kv in a.items() if kv[1] == b]
max_k_list = sorted(max_k_list)
for i in max_k_list:
  print(i)

This time it was ABC's 3 complete, so I could only solve it so far. As a reflection, I couldn't start at 9 o'clock because I was playing the game. The answer speed was extremely slow due to forgetting to sort or doing useless TLE in the C question. Especially today, D was very difficult, so I had to solve up to C quickly. After that, it is necessary to get into the habit of simply solving the problem. .. (I can not seem to do it)

D problem

I tried to implement it by looking at the explanation of Youtube. I didn't notice that it could be solved in a 2-minute search. I wonder if it is necessary to get used to this area.

n, K = map(int, input().split())
a = sorted(list(map(int, input().split())))
inf = 10**18 + 1
l = -1 * inf
r = inf
while(l + 1 < r):
  c = (l + r)//2
  count = 0
  for i in range(n):
    #a[i]Case classification by sign of
    #a[i] <There is a k that can be 0 and k<If j, then a[i]*a[j]Is less than a certain value x.
    if a[i] < 0:
      start = -1 #OUT
      end = n #OK
      while start + 1 < end:
        mid = (start + end) //2
        if a[i] * a[mid] < c:
          end = mid
        else:
          start = mid
      count += (n-end)
      if start < i:
        count -= 1
    else:#a[i]Since the sign of is reversed, the operation opposite to the previous operation may be performed.
      start = -1 #OK
      end = n #OUT
      while start + 1 < end:
        mid = (start + end)//2
        if a[i] * a[mid] < c:
          start = mid
        else:
          end = mid
      count += end
      if a[i] * a[i] < c:
        count -= 1
  count = (count // 2)
  if count < K:
    l = c
  else:
    r = c
print(l)

However, it was TLE. It seems that C ++ can make it in time, but python cannot. .. .. People who are AC seem to be using numpy's np.searchsorted well to solve it.