Educational Codeforces Round 112 (Rated for Div. 2)

A. PizzaForces (00:02, +)

모든 피자의 크기 대비 가격이 동일하기 때문에 만들 수만 있다면 해당 크기에 2.5를 곱한 값이 답이 된다. 6 이상의 모든 짝수를 만들 수 있음이 자명함으로 홀수와 6 미만일 때에만 예외처리를 진행하면 된다.

 

B. Two Tables (01:16, +3)

단순 Case Work 문제지만, 코딩 뇌절으로 인해 가장 늦게 맞춘 문제가 되어버렸다. Case Work 문제일 때에는 손코딩을 하고 들어가는 습관을 기르자.

 

C. Coin Rows (00:36, +)

문제 이해를 잘못해 해결에 오랜 시간이 걸렸다. Alice가 내려갈 칸을 정하면 Bob의 점수는 누적합을 이용해 \(O(1)\) 에 구할 수 있으므로 총 \(O(N)\) 시간에 해결할 수 있다.

 

D. Say No to Palindromes (01:02, +1)

조건을 만족하려면 해당 구간에서 임의의 연속된 세 문자를 골랐을 때에 모두 달라야 한다. 누적합 아이디어를 이용해 해당 구간을 abc, acb..등의 6가지 패턴으로 채우는 비용을 모두 계산해 그 중 최솟값을 출력하면 된다.

 

E. Boring Segments (-4)

문제를 처음 보고, 파라메트릭을 박을 수 있다는 것을 깨닫고 박았다. 이후 Range Min Query with Lazy Propagation을 구현해서 뚝딱 냈다. 내고 보니 1분 전이었고, 해당 제출에서 TLE가 났다. 알고 보니 파라메트릭을 쓰지 않고도 Two Pointer로 해결이 가능해 \(O(NlogN)\)에 해결해야 하는 문제였다. B에 시간을 박지 않았다면 충분히 풀었을 것 같아 아쉬웠다.