Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)

https://codeforces.com/contest/1654

 

E에서의 문제 착각으로 인한 시간 소비 과다. (+ 정해 구현하고도 10회정도 TLE)

F에서 정해를 찾았지만 판단미스로 (알고보니 상당히 복잡한)별해를 구현하다가 시간 끝.

 

A. Maximum Cake Tastiness

 

딱봐도 임의의 i, j에 대하여 이 둘을 인접하게 하는 것이 무조건 가능하므로 답은 a[i] + a[j]의 최댓값이다.

 

B. Prefix Removals

 

딱봐도 largest prefix를 제거하는 것과 그냥 한 char을 제거하는 것과 답이 같다.pf) largest prefix를 제거하지 못하게 되는 순간은 char을 제거하지 못하는 순간과 완벽히 동일하다.

 

C. Alice and the Cake

 

모두가 그랬을 것이라고 생각하지만, [a1, a2, ..]를 이용하여 한 숫자를 만드는 과정을 처음에 고려하였다.-> [1, 1, 1, 1, 1, 1]의 예제를 통해 이게 매우 어려움을 깨닳았다.-> 이후 반대로 특정한 첫 숫자 A(= a1 + a2 +...)를 [a1, a2, ...]로 만드는 과정을 생각하였다.-> 큰 원소들부터 하나하나 만들어주면 AC

 

D. Potion Brewing Class

 

간선이 n - 1개라는 점에서 트리임을 바로 캐치하면 사실 풀이는 직관적으로 생각해낼 수 있다.

-> 모든 소수에 대해서 트리에서 dfs를 해주면 된다.

-> 하지만 위의 풀이상에서는 대략 1e4개의 소수에 대해서 1e5짜리 dfs를 하기에 TLE

-> 그래서 모든 소수가 아니라 꼭 필요한 소수들에 대해서만 계산을 진행해주면 된다.

 

E. Arithmetic Operations

 

TLE를 진심 10번 정도 받았다. 솔직히 N값을 5e4로 설정하더라도 이상한 풀이들이 뚫릴 것 같진 않다.

처음에는 1) a_i가 실수로 변할 수 있다고 생각함 2) a_i가 꼭 i번째 자리일 필요가 없다고 생각함 

 

n이 1e5라는 것은 그렇다 치고 a_i의 범위가 1e5라는 것에 착안 (이 최대치를 m이라 하자)

-> 풀이가 nlgm 혹은 mlgn일 수 있는가?

-> 1) 딱히 이분탐색으로는 안될 것 같음. 

    2) set, map을 이용하고 n번만 계산하는 것도 x

    3) 아주 엄청난 등차수열을 구해주는 기똥찬 자료구조가 존재? -> 어차피 못 만들듯함

-> 제곱 반절 나누기를 고려하였지만, d가 커졌을 때 처리할 방법을 생각해내지 못하였다.

 

-> a[i]의 크기가 1e5이하이기 때문에 반드시 d가 일정 이상의 값을 가지게 되면 더 확인할 필요가 없다는 점

https://codeforces.com/contest/1654/submission/150247329

 

F. Minimal String Xoration

 

이문제는 진짜로 보자마자 suffix array를 떠올렸는데 ㅜㅜ 왜 버렸을까

https://codeforces.com/contest/1654/submission/153551341

구현도 심지어 어렵지 않은...

 

버린 이유는 사실 분할 정복이 가능할거라고 생각했기 때문이다.

-> 관찰해보면 특정 수 x로 xoration을 한다고 가정했을 때 x가 n번 비트를 가지면 그 비트를 중심으로 뒤집힌다.

-> 그렇다면 (1 ~ slen / 2)의 최소와 (slen / 2 + 1 ~ slen)의 최소를 구해서 둘을 합쳐주면 되는 것 아닐까?

-> 문제점 1 : (1 ~ slen / 2)에서의 xoration과 (slen / 2 + 1 ~ slen)의 xoration이 같아야 한다.

-> 해결법 : pair로 어떤 수가 xoration되었는지 같이 기록해준다.

-> 문제점 2 : 근데 만약에 여려 x에 대해서 (1 ~ slen / 2) 값이 같은 최솟값을 준다면 어떻게 하는가

-> (1 ~ slen / 2)를 최소로 하는 여러 개의 x를 가져간다면 "aaaaaaaaaa" 따위에서 무조건 TLE 터진다.

Segtree나 DFS풀이가 있는 거로 보아 위의 풀이가 가능은 하겠지만 구현이 훨씬 좆같다

-> 개중에서 몇몇은 그냥 정해를 분할정복처럼 된 형태일 듯하네요 음...