Educational Codeforces Round 41

링크 : http://codeforces.com/contest/961

아직 시스템 테스트가 남긴 했지만 적당히 5문제 잘 풀었다. E번에서 코드 짜다가 갑자기 생각이 이상해져서 패널티를 많이 먹은게 아쉽다. 처음부터 좀 더 정확하게 생각했으면 패널티를 4~50은 덜 받았을텐데.. 그게 좀 아쉽. D번도 그렇고 E번도 그렇고 코드 짜다가 꼬이는 걸 어떻게 좀 해야할텐데 싶다.

A. Tetris

그냥 나온 숫자들 중에 제일 횟수 적은 거 출력해주면 된다.

B. Lecture Sleep

t 값이 1인 건 다 답에 포함시켜놓고, 맨 앞부터 k개 구간을 유지하면서 그 k개 안쪽에 있는 0인 애들을 다 1로 바꿨을 때의 값을 순서대로 구해서 그 중 최댓값을 출력해주면 된다.

C. Chessboard

완전 구현 문제. 4등분된 조각을 붙이고 / 색칠하는 모든 경우에 대해 최솟값 구해서 출력해주면 된다.

D. Pair Of Lines

1-2 점이 같은 라인에 있는 경우, 1-3 점이 같은 라인에 있는 경우, 2-3 점이 같은 라인에 있는 경우 세 가지만 확인하면 된다.

1-2 점이 같은 라인에 있는 경우가 안 된다면 -> 1번 점과 2번 점은 반드시 서로 다른 라인 위에 존재해야 한다. 그러면 이제 이 경우, 또 다른 3번 점에 대해 이 점이 1번 점과 같은 라인 위거나 아니면 2번 점과 같은 라인 위거나 두 가지 경우밖에 남지 않는다(둘 중 한 라인에는 반드시 속해야 하기 때문). 따라서 모든 경우를 저 3가지로 커버 가능하므로, 3가지 경우에 대해 전체 N개 점을 순회하며 그렇게 점 집합을 구분할 수 있는지 확인해주면 된다.

E. Tufurama

i번째 시즌에 대해서, i+1~ai 시즌까지 중 에피소드가 i이상인 것들의 개수를 모두 구해 더해주면 답이 된다. 이걸 구하는 방법은 굉장히 여러 가지가 있을 수 있는데, 나는 펜윅으로 했다. i번째 시즌 루프에서 배열에 k번째 원소= k번째 시즌이 에피소드가 i이상이면 1, 아니면 0으로 정의하고 여기서 펜윅트리를 이용해 구간합을 빠르게 구한다. 저런 배열을 유지하는 건 간단한데, 에피소드가 동일한 시즌들을 모두 미리 묶어 놓은 후 시즌 i번째 루프를 지나갈 때 에피소드가 i이 모든 시즌들을 다 배열에서 제거해주면 배열에는 항상 에피소드가 i보다 큰 시즌들만 남아있게 된다.