AtCoder Beginner Contest 248

A. Lacked Number (0:01, +) *22

B. Slimes (0:02, +) *41​

생략

 

C. Dice Sum (0:05, +) *787

C번치고 어려워서 놀랐다. \(DP[i][j]\)를 i번째 주사위까지 봤을때 합이 j인 경우의 수로 정의하면 \(O(N^4)\) 정도에 문제를 해결할 수 있다.

 

D. Range Count Query (0:06, +) *793

같은 숫자들에 대해 등장하는 인덱스를 벡터에 저장해 준 후 lower bound와 upper bound를 적절히 사용해 개수를 구해주면 된다.

 

E. K-colinear Line (0:15, +) *1292

고려해야 하는 직선의 개수가 \(O(N^2)\)개이고, 이에 대해 \(O(N)\)으로 주어진 조건을 만족하는지 확인할 수 있다. 따라서 중복 처리만 잘 해주면 되는데, 이는 \(ax+by+c=0\)의 각 계수를 최대공약수로 나눠준 후 map등을 통해 체크해주면 된다.

 

F. Keep Connect (1:19, +) *1828

​각 칸에 대해 상태를 잘 정의해주고, \(DP[i][j][state]\)를 i번째 칸의 상태가 state일 때 j개를 뺀 채 만들 수 있는 경우의 수로 정의하면 문제를 해결할 수 있다. 

 

E까지 풀었을 때 34등인가 그랬는데, F를 너무 느리게 풀었다..