AtCoder Regular Contest 172

https://atcoder.jp/contests/arc172/tasks

AGC는 너무 어렵고, ABC는 너무 스탠다드하다. (교육용이란걸 생각하면 적합한 편)

적당히 똥맛이 나며, 난이도가 오락가락한 ARC를 그렇기에 좋아하는 편이다.

앳코더가 확실히 수학 공포증만 없으면 재밌는거 같긴 하다 ㅋㅋ

버추얼로 맛을 봤다.

 

A. Chocolate

 

처음에 곧바로 꽂힌 아이디어가 있다.

적당히 그리디하게 앞에서부터, 큰 블록부터 되는대로 넣으면 되지 않을까?

예를 들어 적당히 x = 0에서는 W만큼의 여유가 있다고 생각할 수 있다.

여기에 들어가는 제일 큰 블럭인 2^A을 넣는다면, 앞으로 남는 여유는 W - 2^A.

이후 0 <= x < 2^A는 남는 여유가 W - 2^A이고, 2^A <= x는 다시 여유가 W가 된다고 생각할 수 있다.

이러다 또 2^B 크기의 블럭을 넣는다면,

0 <= x < 2^B에서는 W - 2^A - 2^B, 2^B <= x < 2^A에서는 W - 2^A, 2^A <= x에서는 W라고 여길 수 있다.

2^X는 서로 배수가 된다는 특징으로 인해서, 위의 풀이는 맞는 풀이이다... (구현실수로 WA)

 

2^X임을 살짝 망각하여 위의 풀이가 틀렸다고 착각하였고, 그리디함을 줄인 더 안전한 풀이를 구상하였다.

A >= 1인 A에 대해서는 사실 그냥 H / 2 * 2, W / 2 * 2 짜리 초콜릿을 나눈다고 생각해도 별 상관 없다.

따라서 남는 H * W - (H / 2 * 2) * (W / 2 * 2)만큼을 A = 0인 친구들에게 나누어준다.

이를 지속적으로 진행해주면 된다.

즉, 남는 H * W - (H / 2 * 2) * (W / 2 * 2)만큼을 A = i인 친구들에게 나누어지고,

A = i에게 나누어지고 남는다면, 또다시 A = i - 1, i - 2, .. .0으로 더 작은 조각을 원하는 친구들에게 주면 된다.

 

B. AtCoder Language

 

문제에서 주어지는 조건은 그냥 같은 단어가 N - K이상 떨어져 있다는 뜻이다.

따라서 그냥 P(N, N - K) * (L - (N - K)) ^ K가 된다.

 

C. Election

 

2번째 voter부터 N번째 voter까지의 진행 중에 1번째 vote를 끼워넣는다고 생각해보자.

편의를 위해서 1번째 vote는 무조건 'A'라고 생각하자.

1번째 vote이 맨 마지막에 들어가는 경우를 기준으로 생각하자 (ans = 1)

이후 기준이 되는 result과 즉각적으로 result가 달라지는 경우만 고려하자. (달라질 때마다 ans++)

예를들어 vote[i] = 'A'인데 i번째 vote 앞에 1번째 vote를 끼워넣을 경우, 어차피 똑같은 표가 들어가서 바뀌지 않는다.

 

따라서 무조건 vote[i] = 'B'의 앞에만 끼워넣어야 한다.

하지만 즉각적으로 결과가 바뀌려면 (현재까지 A의 득표수) - (현재까지 B의 득표수) = S[i] 라고 할때,

S[i] = -2, -1, 0 중 하나여야만 한다.

원래 S[i]값에 비해 1번째 표가 들어가면 S[i] + 2가 되니 때문에 provision이 바뀌는 경우는 저 세 경우이다.

따라서 vote[i] = 'B'이고, S[i] = -2, -1, 0인 경우만 세면 된다. (맨 처음의 1을 잊지 말 것)

 

E. Last 9 Digits

 

D를 감도 못 잡고 있다가, E의 솔브수를 보고 호다닥 도망왔다. (결국 시간내에 못 품...)

일단 이거 그냥 좀 굴려보면, 답이 안 겹친다는 것을 알 수 있다.

일일이 modpow(X, X)가 처음 등장하는지 코드를 굴려보면 잘 굴러간다.

이러한 발견에서부터 출발했기 때문에, 뒤의 풀이도 완전 엄밀하진 않고, 수학 좋아하면 공식 에디토리얼 참고

 

그러다보면 다음과 같은 사실을 발견할 수 있다.

claim) X = 1e6 * p + q (단, p < 1e3, q < 1e6)라면, \(X^X \equiv q^q (mod \,\,1e6)\)

pf) 우선 X는 2나 5의 배수가 아니기 때문에 q 또한 2, 5와는 서로소이다.

-> \(X^X \equiv q^q (mod \,\, 2^6)\), \(X^X \equiv q^q (mod \,\,5^6)\) 을 각각 보이면 충분하다

-> 이때 q가 2, 5와 서로소이기 때문에, 오일러 정리를 사용해주면 된다.

 

따라서 위의 claim에 의해 q = 0 ~ 1e6에 대해서 q^q의 마지막 9자리를 미리 계산해둔다.

이후 1000개의 p 값을 단순히 모두 대입해서 답이 되는지 확인해보면 된다.

 

D. Distance Ranking

 

솔직히 답이 존재할 것은 그리 의심되지 않는데, 정수점에 점을 배치한다는 것이 참 막막하다.

N = 20인 모양새를 보니 비트마스킹도 조금 의심되긴 하는데 도대체 비트마스킹은 써먹을 구석이 없어 보인다.

솔직히 대충 미지수만 N^2개이고, 식도 N*(N-1)/2개인 방정식은 풀기 겁나고 (풀 수 없을 거 같고)..

그래서 생각한게 (x, 0, 0, ..), (0, y, 0, ...), (0, 0, z, ...) 같은 방식인데 이건 너무 변수가 부족하여 없을 수 있다.

 

풀이가 생각보다 간단하다.

정확히 에디토리얼과 같은지는 모르겠지만, 내가 이해한대로 설명하겠다.

우선 N개가 서로 거리가 모두 동일하도록하는 방법은 (1, 0, 0, ..), (0, 1, 0, ...), (0, 0, 1, ...)...으로 모두 1로 하면 된다.

그러면 아주아주 작은 epsilon들을 생각해보자. -> 기존의 모든 좌표를 조금씩, e[i][j]씩 shift하자.

즉, (1 + e[1][1], e[1][2], e[1][3], ..), (e[2][1], 1 + e[2][2], e[2][3], ..)로 설정할 수 있다.

설정상 epsilon은 매우 작으니, i번점과 j번 점 사이의 거리는 대충 2 + 2(e[i][i] - e[j][i]) + 2(e[j][j] - e[i][j])이다

여전히 변수가 4개씩 박히는 부등식이 N*(N-1)/2개나 있는 끔찍한 모양새이다.

 

어차피 수식은 N * (N - 1) / 2개 밖에 안되니까, 남아도는 변수들을 정리해버리자

-> e[p][p] = 0, e[p][q] = e[q][p]라고 멋대로 정해버리자.

이렇게 정해버리더라도 어차피 정확히 변수가 N * (N - 1) / 2개 남고, i와 j의 거리는 단순하게 -4e[i][j]이다.

따라서 문제에서 주어지는 d(pA1, pB1) < d(pA2, pB2) < ....은 e[A1][B1] > e[A2][B2] > ...로 정할 수 있다.

 

실제로는 0~1e8의 정수를 사용해야하므로, 기본 설정이  (1, 0, 0, ..), (0, 1, 0, ...), (0, 0, 1, ...)...면 안된다.

-> ans[Ai][Bi] = ans[Bi][Ai] = N^2 - i로 배정해주고, ans[x][x] = 1e8로 설정해주면 된다.

-> N^2 << 1e8이므로, 위에서 설명한 것에 의해서 조건을 만족하게 된다.