ABC337 E - Bad Juice

Competitive Programming C++

2024-01-21

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc337/tasks/abc337_e

원문 링크
https://atcoder.jp/contests/abc337/editorial/9140

부를 사람의 수가 \(M\)명일 때, 다음 날 각 지인이 배탈이 난 정보 \(S\)의 경우로 가능한 것은 최대 \(2^M\)개이기에, \(N\)개의 주스 중 상한 주스의 번호를 \(S\)의 정보로부터 식별하는 데는 \(2^M \geq N\), 즉 \(M \geq \lceil \log_2N \rceil\)일 필요가 있습니다.

반대로, 부를 사람의 수는 \(b:=\lceil \log_2N \rceil\)명이면 충분합니다. 실제로 다음과 같은 방법을 통해 \(b\)명의 지인을 이용해 상한 주스를 특정할 수 있습니다.

편의상 주스의 번로와 지인의 번호를 \(0\)부터 시작하는 것으로 두고, 각각 \(0, 1, 2, …, N - 1\)과 \(0, 1, 2, …, b - 1\)이라고 합시다. 이 때, \(2^b - 1 \geq N - 1\)이므로, 모든 주스의 번호를 \(b\)자리의 2진수로 표현할 수 있습니다. 이 2진수의 각각의 비트들을 맨 아래 자리부터 순서대로 \(0, 1, 2, …, b - 1\)번째 비트라고 번호를 붙입니다. 그리고 다음과 같이 각 지인에게 마시게 할 주스의 조합을 결정합니다.

지인 \(i = 0, 1, 2, …, b - 1\)과 주스 \(j = 0, 1, 2, …, N - 1\)의 각각의 쌍 \((i, j)\)에 대해, \(i\)번째 지인에게는 주스의 번호 \(j\)를 2진수로 표현했을 때 \(i\)번째 비트가 켜져 있는 \(j\)번째 주스를 마시게 한다.

이 때, 상한 주스의 번호 \(X\)를 2진수로 표현한 것의 \(0, 1, 2, …, b - 1\)번째 자리와 문자열 \(S\)의 \(0, 1, 2, …, b - 1\)번째 자리가(처음 문자를 \(0\)번째 문자라고 하면) 일치하며, \(X\)를 \(S\)로부터 한번에 특정할 수 있습니다.

해밍 코드

문제 자체는 해밍 코드(Hamming codes)라고 해서 잘 알려진 듯 하다.

… 내가 모른다는 것만 빼면.

D까지 30분만에 해치우고 빨리 E를 봐서 오늘은 E 풀겠구나 했더니 나만 모르는 웰노운에 당해버렸다.

더 공부해서 이런 일이 없게 해야지 원.