AtCoder Beginner Contest 327

맛잇다

 

A - 구현하면 됩니다.

 

B - 구현하면 됩니다. 오버플로우 신경쓰기 싫어서 저는 파이썬을 사용했습니다. 여담으로 1 이 입력으로 들어오는 경우를 조심해야 합니다. 저는 조심 못해서 1틀함...

 

C - "구현"하면 됩니다. 끔찍하지만 이쁘게 짤 생각을 안하고 ctrl C + ctrl V 를 많이 하면 편합니다.

 

D -

$S_i$ 와 $T_i$ 의 값이 달라야하며, 각 값은 0 또는 1 밖에 나올 수 없습니다. 이는 조금 생각해보면 $S_i$, $T_i$를 잇는 양방향 간선이 있는 그래프가 주어졌을 때, 이분 그래프인지 판별하는 문제로 환원할 수 있습니다. $S_i = T_i$ 인 케이스만 따로 예외처리 해줍시다.

 

E - 

같은 $K$에 대해, 답에 영향을 주는 부분은 분모에 있는 합 부분입니다. 결국 $K$개의 원소들의 합을 최대화 하는 문제이고, $dp(i, j)$ 를 $K = i$ 일 때, $j$번째 원소를 마지막으로 선택했을때의 합 이라고 정의해줍시다. 그럼 상태 전이는 $dp(i, j) = \max_{t < j} dp(i - 1, t) * 0.9 + P_j$ 가 됩니다.

 

F - 

$(T_i, X_i)$를 2차원 좌표평면의 점으로 생각했을 때, $[S, S + D)$ $\times $ $[L, W)$ 영역에 있는 점의 개수의 최댓값을 구하는 문제가 됩니다. $T_i$가 $[t, t + D)$ 사이에 있는 점들을 슬라이딩 윈도우 등으로 관리하고, 각 $X_i$에 대해, $[X_i, X_i + W)$ 구간에 값을 더하고 최댓값을 저장할 수 있는 자료구조로 문제를 풀면 됩니다. 이는 레이지 세그먼트 트리 등으로 해결할 수 있습니다.

 

후기 - 

공부하기 싫어서 앳코더를 쳤는데, 인생 맥퍼포를 찍었습니다. 

 

B는 1인 케이스를 생각 안해서 1틀, E는 python은 tle여서 pypy로 제출했더니 AC(...) 여서 1틀, F는 그냥 너무 생각을 안하고 처음에 제출해서 1틀 (...) 전체적으로 좀 반성할 점이 있었습니다. 특히 E는 처음에 문제를 잘못 읽어 이상한 코드를 짰네요.... 이러한 이상한 실수들만 없었다면 옐로우 퍼포를 찍지 않았을까? 싶어서 더 아쉽습니다.

 

셋 자체는 재밌었습니다. 문제들이 참신한가? 하면 잘 모르겠는데.. 앳코더가 원래 그런가봐요