AtCoder Beginner Contest 187 A〜C問題
前書き
AtCoder Beginner Contest 188 A〜C問題を解きました。
A問題
難易度：灰
時間：4分
A,B = map(str,input().split()) A = sum(list(map(int, list(A)))) B = sum(list(map(int, list(B)))) print(max(A,B))
B問題
難易度：灰
時間：8分
工夫した点としては、傾きを求める際に-1≤(yj-yi)/(xj-xi)≤1となれば良いと単純に考えがちです。
xj=xiの時に分母が0での除算にならないよう処理します。
import itertools N = int(input()) xy = [list(map(int,input().split()))for n in range(N)] N_ = list(itertools.combinations(range(N),2)) count=0 for ij in N_: if abs((xy[ij[0]][1]-xy[ij[1]][1]))<=abs((xy[ij[0]][0]-xy[ij[1]][0])): count+=1 print(count)
C問題
難易度：灰
時間：35分
最初何回考えても TLEで解けへんやろと勘違いしていました。
Set型でin setや辞書型のKeyでin hogehoge.keys()とする時は、
List型でin listとする時より同じ処理でも格段に速度が向上するようです。
List型での検索→O(n)
Set型での検索→O(1)
今回は完全一致の文字列を探していきます。
その際にSet型にすると文字列をハッシュ値に切り替えて、探索してくれるみたいです。
今回では上記を応用して問題を解きます。
import sys N = int(input()) normal, abnormal=set(),set() for n in range(N): s = input() if s[0]=='!': abnormal.add(s[1:]) else: normal.add(s) for n in abnormal: if n in normal: print(n) sys.exit() print('satisfiable')
