A. 20213 Adversarial Memory

1~N 2쌍의 2N개의 뒤집어진 카드가 있고, 그 중에 2개의 카드를 뒤집어서 맞추면 빼는 게임을 할 때, 적당하게 카드를 보여줘서 2N-1 번 안에 게임이 끝나지 않도록 인터랙티브로 카드 값을 줘라

뭔가 코포에 나올법한 인터랙티브 문제.

핵심은 정보를 최대한 숨기는거고, 1번혹은 2번 등장 할 수 있으니까 각각 set에 넣어서 구분해줬음. 코포에서 뉴비들이 set많이 쓰던데 set이 진짜 개꿀이더라. 시간복잡도 상관없을 때 쓰면 중복 처리 개쉬움

대회때 잘못 생각한 내용은 무조건 한 번도 안 보여준 값을 주고 그게 안되면 한 번 나온 값을 주면 된다는 거

이렇게 하면 1~N까지 다 찾은 다음에 아무거나 하나 뒤집어서 나오는걸 1 ~ N 에 대응시킬 수 있음. 이러면 N번인가 만에 끝날거임 아마

가장 좋은 점은 처음 깔 때는 지금까지 처음 보는거 ( 그래야 2번째에 바로 맞춰서 못 가져 감 ), 2번째 깔 때는 지금까지 본 적 있는 거 (그래야 정보를 최소한으로 줄 수 있음)

결국 까는 사람의 목표는 최대한 많은 숫자를 처음으로 보는거. 그래야 모르는 카드를 까서 아는 숫자가 나오면 바로 끝낼 수 있으니까

근데 본 적 있는 숫자를 처음에 보여주면 말짱 꽝임. 걍 그거 까버려서 끝내니까. 그래서 처음 뒤집는건 한 번도 안 나온거, 2번째 뒤집는건 한 번 이상 나온거 (다만 당연히 짝 되면 안 됨) 

그리디를 생각할 수 있고 짜면 됨. 2N-1 이 나오는건 잘 모르겠는데 증명이 있는 듯? 문제 이름 그대로 구글에 검색하면 1번째로 나오는 논문에 써져있다더라

전체 후기 

8솔했고 업솔빙으로 9솔까지 했음. 

D같은거에서 시간 쓴거랑 H에서 삽 한 번 푼게 아쉽지만 괜찮다

확실히 힐링셋이라고 불리는 이유가 있음;; 존나 쉽더라

그래도 A, I, H 는 문제 재밌었던 것 같아 만족. 팀원 중에서 DP 문제 담당하는 쪽으로 DP 열심히 파봐야겠음