[AtCoder] Beginner 402

https://atcoder.jp/contests/abc402

A

upper case만 출력하기

B

Queue로 넣고 빼고 구현

C

모든 dish의 ingredient의 개수의 합은 최대 3*10^5 라고 명시되어있다.
따라서 아래 코드가 3*10^5 블럭 개의 코드가 수행됨을 알 수 있다.

for dish in dishes:
 for ingredient in dish:
   # do something

overcomes ingredient는 dictionary를 사용하여 빠르게 탐색할 수 있도록 했다.

import sys
from collections import deque
r=sys.stdin.readline

N,M=map(int,r().split())
dishes = []
for _ in range(M):
    a, *arr = map(int,r().split())
    dishes.append(arr)
b = list(map(int,r().split()))
dic = {}
days=1
for e in b:
    if not e in dic:
        dic[e]=days
    days+=1

numbering=[0]*(N+1)
for dish in dishes:
    tmp = 0
    for e in dish:
        tmp = max(tmp, dic[e])
    numbering[tmp] += 1

for i in range(N):
    numbering[i+1] += numbering[i]
print(*numbering[1:],sep='\n')

D

Line Crossing
N이 짝수 홀수 일 때 다를 것 같아서 관찰을 해봤다.
N=5, N=6 일 때를 전부 해봤더니 의외로 기울기가 같은 직선의 쌍이 많았다.
결론은, 점 번호 a,b,c,d 에 대해 직선 (a,b)와 직선(c,d)가 기울기 같다 <=> (a+b)%n = (c+d)%n 이다.

import sys
from collections import deque
r=sys.stdin.readline

N,M=map(int,r().split())
dic = {}
lines = []
for _ in range(M):
    A,B=map(int,r().split())
    lines.append((A,B))
    tmp = (A+B)%N
    if not tmp in dic:
        dic[tmp] = 0
    dic[tmp] += 1

ans = 0
for a,b in lines:
    tmp = (a+b)%N
    ans += M-dic[tmp]
print(ans//2)