ABC155の振り返り

初めての投稿です。よろしくお願いします。練習で昨日行われたABC155の振り返りをまとめてみます。

#A問題
###問題文
3つ組の数について、ある2つが等しく、残りの 1つがそれらと異なるとき、その3つ組を「かわいそう」であるといいます。3つの整数 A,B,Cが与えられるので、この3つ組がかわいそうであれば Yes を、そうでなければ No を出力してください。

###解答例

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

集合set()を使いその要素数を見ることでかわいそうかそうでないかを判定できる。

#B問題
###問題文
あなたは AtCoder 王国の入国審査官です。入国者の書類にはいくつかの整数が書かれており、あなたの仕事はこれらが条件を満たすか判定することです。規約では、次の条件を満たすとき、またその時に限り、入国を承認することになっています。書類に書かれている整数のうち、偶数であるものは全て、3または5で割り切れる。上の規約に従うとき、書類にN個の整数 A1,A2,…,ANが書かれた入国者を承認するならば APPROVED を、しないならば DENIED を出力してください。

###解答例

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")

もし偶数で3か5で割り切れないものがあればflagを書き換えてbreakさせる。最後にflagの値に応じて出力する。

#C問題
N枚の投票用紙があり、$i\ (1≤i≤N)$ 枚目には文字列 $S_i$が書かれています。書かれた回数が最も多い文字列を全て、辞書順で小さい順に出力してください。

最初dictを作成してkeyに文字を, valueに出現回数を入れる形で作成した。。。らTLEした。今日は上手くいかないフラグがたった予感がした。

###解答例(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)

ここでTLEする要因は恐らく最初のfor 文と　そのあとの　if not s in dic:で$O(N^2)$に近い計算になってしまっているからだと考えられる。（もし違ったらコメント頂きたいです）
max_k_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]
で毎回for文の中で最大値を取得していることで$O(N^2)$になっていました。最大値は変わらないのでループの外で取得しておくことで無駄な計算を削ることができ、$O(N)$にできます。(ACの時にこっちも変更してたのを忘れてました。。。)
最終的にcollectionsのモジュールを使えばいい話だった。
###解答例(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)

今回はABCの3完だったのでここまでしか解けなかった。
反省点としてはゲームをしていたせいで9時から始められなかったこと。C問題でソート忘れたり無駄なTLEをしたりで解答速度がめちゃくちゃ遅かったこと。特に今日はDが激難だったのでCまでを速く解く必要があった。あとはシンプルに普段からコツコツ解く習慣を付ける必要がある。。（なかなかできない）

###D問題

Youtubeの解説をみて実装してみた。2分探索で解けることに気付かなかった。ここら辺は慣れが必要なのかな。

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]の符号で場合分け
    #a[i] < 0 の場合あるkが存在してk < jならばa[i]*a[j]はある値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]の符号が逆なので前と逆の操作を行えばよい。
      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)

ところがTLEでした。C++では間に合ってもpythonじゃ間に合わないみたいです。。。
ACしている人たちはnumpyのnp.searchsortedを上手く利用して解いているみたいでした。