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.

Recommended Posts

Looking back on ABC155
Looking back on 2016 in the Crystal language
Looking back on learning with Azure Machine Learning Studio
Looking back on creating a web service with Django 1
Looking back on the transition of the Qiita Advent calendar
Looking back on creating a web service with Django 2
ABC168
ABC164
Atcoder ABC125 C --GCD on Blackboard
ABC174
[Python] Looking back on what I taught programming beginners from functions
ABC175
ABC170
ABC182
ABC153
[Spotify API] Looking back on 2020 with playlists --Part.1 Acquisition of playlist data
Looking back on the 10 months before a programming beginner becomes a Kaggle Expert
[Spotify] Looking back on 2020 with playlists --Part.2 EDA (basic statistics), data preprocessing
I looked back on Python classes again
Looking back on how the office worker changed jobs as an engineer (Part 2)
Looking back on the machine learning competition that I worked on for the first time
Looking back on the history of expressions that return sum of square to Pythonic