scpc 2차 예선 후기

풀이를 구체화하는 능력이 너무 부족하다.....

 

 

1 - 수열연산

투 포인터로 가장자리부터 깎아주면 된다.

 

2 - 반 협동게임

각 수 별로 가장자리부터 깎아서 순서쌍들을 다 모으자. 이를 정렬하고 왼쪽부터 보면 된다. 배열 크기를 잘못 잡아서 6번이나 제출을 날렸다. 이거때문에 멘탈이 흔들렸다.

 

3 - ABC

dp[x][c][k] = x번 정점에서 알파벳이 c이고 k번 스킵했을 때의 최대 길이로 정의했지만, 여기서 사이클 찾기랑 막 뇌절하면서 그대로 침수.. k=0인 경우만 긁었다.

 

4 - 직사각형

1x1 사각형에서 NxN까지 늘리려면, 어자피 2N-1번만 늘리면 된다. O(N^3)에 가능하다.

근데 이를 깨닫지 못했다. 어떤 수 x와 y에 대해, y - x + 1와 x~y의 수들을 모두 포함하는 최소 직사각형의 넓이가 같은지 확인하며 ans를 갱신해가는 O(N^4) 풀이로 긁었다.

 

 

 

 

너무 멍청하다.