Codeforces Round #485 (Div.2)

이번꺼는 버추얼후기.

A. Infinity Gauntlet

map을 적극 활용하자. map이 없다고? 거짓말하지마세요 그런언어가 어딨어.

source : https://codeforces.com/contest/987/submission/65464832

B. High School: Become Human

x^y 과 y^x을 직접 구해서 비교하려면 당연히 터진다.
양 변에 로그를 씌워서 ylogx와 xlogy를 비교하자.

source : https://codeforces.com/contest/987/submission/65465055

C. Three displays

i<j<k 이면서 s_i<s_j<s_k 인 i,j,k 중 c_i + c_j + c_k 가 최소가 되는 값을 찾아야한다.
어렵게 생각할 필요없이 j인덱스를 하나 잡으면 (j,N] 구간에서 s_j 보다 큰 s_k 중 가장 작은 c_k를 찾고 [1,j) 구간에서 s_j 보다 작은 s_i 중 가장 작은 c_i를 찾으면 된다. j가 [1,N]에서 하나씩 본다고 생각하면 O(N²). N이 3천이니 충분히 가능하다.
나는 멍청하게 N²을 보면서 한쪽구간을 세그로 찾는 창조적 시간낭비를 하긴 했는데 만약 이 문제가 요새 코포에 나왔다면 N<=10⁵에 O(NlogN)정도의 풀이를 요구하는 문제로 나오지 않았을까 하는 생각이 든다.

source : https://codeforces.com/contest/987/submission/65465868

D. Fair

각 마을에서 s개만큼의 물건종류를 확보하려할 때, 가장 적게 드는 비용을 마을별로 찾아야한다.
한 번에 답을 구하려하면 상당히 어려워진다. 1<=k<=min(n,100) 이라는 조건에 주목해서 k를 하나씩 보면 쉽지않을까? 라는 발상을 해보자. k를 하나씩 본다면 어떤 마을에서 k번째 물건을 확보하는 비용은 당연하게도 k를 가지고있는 마을까지의 최단거리가 될 것이다. 따라서 [1,k]까지 하나씩 보면서 모든 마을에서 k를 가지고있는 마을까지의 최단거리를 bfs로 찾으면된다. 즉, bfs를 k번 돌리고 그 중 가장 작은 s개의 값의 합을 마을마다 출력해주면 끝.

source : https://codeforces.com/contest/987/submission/65467991

E. Petr and Permutations

[1,N] 으로 이루어진 수열에서 petr는 3N번을 임의로 swap하고, Alex는 7N+1번을 임의로 swap한다고 한다. 이 때 swap이 끝난 배열을 보고 누가 swap을 했는지 찾아내야하는데, 문제를 읽고나면 뭘가지고 찾으라는거지? 라는 생각이 들 수 있다. 주어진건 3N과 7N+1이라는 정보밖에없는데 아니 왜 뒤에는 +1을 붙였지라는 점에 주목해보자. 3N은 홀수*N이고 7N+1은 홀수 * N + 1 이다. 앞을 홀/짝으로 나눴으니 N도 홀/짝으로 나눠서 생각해보면 N이 짝수라면 3N은 짝수가 나올것이고 7N+1은 짝수가 나온다는걸 알수있다. N이 홀수면 물론 반대로.
그럼 주어진 수열을 가지고 1..N으로 이루어진 원래 수열을 만드는데 필요한 swap횟수를 cnt라 하면 N이 짝수일때 cnt가 홀수면 7N+1번 swap을 한 것이고 cnt가 짝수면 3N번 swap을 했다는것이 보일것이다.

정리하면
N even && cnt even => Petr
N even && cnt odd => Um_nik
N odd && cnt even => Um_nik
N odd && cnt odd => Petr

source : https://codeforces.com/contest/987/submission/65466411

Um_nik을 Un_nik으로 썼다가 한 번 틀렸다. 아..