Codeforces Round 1037 (Div. 3)

 

분명 대회 종료 당시에는 8문제중 7솔이였는데.. 자고 일어나니까 F 핵당하고 일과 끝나고 보니 B가 시스페일 뜨면서 등수가 확 떨어졌다.

B만 맞았어도 민트로 올라가는 레이팅인데 너무 아쉬움이 많이 남는 대회다.

 

A번 00:02 AC

x의 각 자릿수중에 가장 작은 수가 y임이 자명하다.

 

B번 00:07 AC -> TLE(System testing)

0이 k개 연속되어있으면 등산 횟수를 올리고 날짜는 다음 다음날부터 다시 시작한다.

..였는데 n이랑 k 제한인 10^5를 10^4로 생각해서 코드가 O(n*k)로 구현되버렸다. 아니 그냥 반복문 돌려도 될것을 굳이 짧게 적겠다고..

C번 00:28 AC
a > b 라고 할때, 현재 위치로부터 높이가 a인 탑을 a초 소모해서 가는것보다, b탑을 b초 소모해서 텔레포트하고 a탑을 a-b초 소모해서 텔레포트하는게 더 이득이다. 즉, 작은 탑부터 올라가는게 항상 최선이다. 정렬하고 그리디하게 가능한지 여부만 보면 된다. 도착전 현재 탑 높이보다 시간이 작아야한다는걸 유의하자.

E번 00:45 WA

배열 두개를 헷갈려서 i와 i+1을 바꿔적는 바람에 틀렸다. 찾기가 너무 어려워 10분정도 버렸다. 그 와중에 공교롭게도 테케1은 통과했다.

 

E번 00:54 AC
p[i-1] % p[i] == 0, s[i+1] % s[i] == 0을 만족하는지 확인해야한다. 오른쪽으로 갈수록 나눠져야하기때문. 이후 p[n] == s[1] 으로 전체 GCD가 같은지 확인하는걸로 구현할 수 있다.

 

F번 01:12 TLE

아무 생각없이 색 바뀌는거만 인접한 노드를 정직하게 처리해줬다.

 

F번 01:16 TLE

상수 커팅했으나 별 의미는 없었다. 아이디어 안떠올라서 패스.

 

D번 01:29 AC
C풀고 처음 봤을 때 지문 이해가 안되서 빠르게 패스했다가 F 모르겠어서 돌아왔다.

코인 수가 늘어나면 방문할 수 있는 카지노도 늘어난다. 현재 코인 수에서 갈 수 있는 카지노중에 real이 가장 큰 카지노부터 그리디하게 방문하면 되며, 우선순위 큐를 사용하면 된다.

G1번 02:05 AC
min 후보 x에 대해서 x보다 작은 수는 제외하고 1부터 배열에 최댓값까지 이분탐색으로 해서 조건 만족하면 배열 최대 쌍을 갱신해줄 수 있다. 여기서 조건을 만족한다는건 x나타나는 순간까지 누적합보다 그 구간에서 점수 누적합이 같거나 커진다는것을 의미한다. 범위가 1~100으로 작기 때문에 그냥 1부터 100까지 고정시켜가며 구하면 된다.

 

F번 02:13 AC -> TLE(Hacked)

말을 들어보니 해시핵 방지 안하면 죄다 터진다고 한다. 이런 부조리한게 있을수가..