DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

012

문제로 돌아가기

해설

승리 경계 공격자가 항상 이기는 데 필요한 비교 횟수의 최솟값은 다음과 같다.

Q(N)=⌈3N2⌉−2.Q(N)=\left\lceil\frac{3N}{2}\right\rceil-2.Q(N)=⌈23N​⌉−2.

따라서 M≥Q(N)M\geq Q(N)M≥Q(N)이면 공격자, 그렇지 않으면 수비자를 선택한다.

공격 전략: 상한 서로 다른 두 값의 대표 L<HL<HL<H를 찾는다. 그 전의 같은 값들은 하나의 그룹으로 모은다. 세 값의 대소 관계가 한 번 확인되면 가운데 값은 반드시 111이다. 이후에는 나머지 각 위치를 그 대표와 한 번씩 비교하면 값을 알 수 있다.

아직 세 값을 찾지 못했다면, 처리한 위치들은 두 그룹 L<HL<HL<H에 속한다. 새 위치 두 개 a,ba,ba,b를 묶어서 처리한다. 먼저 둘을 비교한다.

  • a=ba=ba=b이면 하나의 그룹으로 취급하여 LLL, 필요하면 HHH와 비교한다. 총 세 번 이하이다.
  • a<ba<ba<b가 되도록 이름을 정한 뒤 aaa와 을 비교한다. 이면 로 가운데 값이 정해지고, 를 과 한 번 비교하면 된다.

각 쌍은 세 번 이하의 비교로 처리된다. 마지막에 한 위치가 남으면 두 번 이하가 필요하다. 세 값이 모두 등장하므로 끝까지 세 번째 값이 나오지 않는 경우는 없다.

처음 서로 다른 대표를 얻기 전에 같은 값임을 확인한 위치의 수를 eee라 하자. 처음 e+2e+2e+2개 위치에는 e+1e+1e+1번의 비교를 쓴다. R=N−e−2R=N-e-2R=N−라 하면 총 비교 횟수는 이다. 가운데 값을 일찍 찾은 경우에는 남은 위치당 한 번만 비교하므로 더 늘어나지 않는다.

수비 전략: 하한 DSU로 같다고 답한 위치들을 묶고, 각 그룹에 미분류, 낮음, 높음 중 하나의 상태를 둔다. 엄격한 비교는 항상 낮음에서 높음으로 향하도록 유지한다.

  • 미분류 두 그룹을 비교하면 서로 다르다고 답하고 각각 낮음, 높음으로 지정한다.
  • 미분류와 낮음을 비교하면 미분류가 더 크다고 답하고 높음으로 지정한다. 미분류와 높음이면 반대로 처리한다.
  • 서로 다른 낮음 그룹끼리 또는 높음 그룹끼리 비교하면 같다고 답하고 합친다.
  • 낮음과 높음은 낮음이 더 작다고 답한다. 이미 같은 그룹이면 같다고 답한다.

미분류 그룹이 없고 그룹 수가 둘이 되려면, 먼저 NNN개 위치를 분류하는 데 최소 ⌈N/2⌉\lceil N/2\rceil⌈N/2⌉번의 비교가 필요하고, 별도로 N−2N-2N−2번의 병합이 필요하다. 따라서 최소 Q(N)Q(N)Q(N)번이 필요하다.

그보다 적은 비교 후에는 항상 서로 다른 유효한 수열 두 개를 만들 수 있다. 미분류가 남아 있고 낮음·높음 그룹이 있다면, 각각의 값을 (0,2,1)(0,2,1)(0,2,1) 또는 (1,2,0)(1,2,0)(1,2,0)으로 지정한다. 여기서 순서는 낮음, 높음, 미분류이다. 아무 비교도 없으면 서로 다른 두 유효한 수열을 임의로 고른다. 미분류가 없다면 낮음 또는 높음 중 적어도 한쪽에 그룹이 둘 이상 있다. 다른 쪽을 끝값으로 고정하고, 그쪽의 서로 다른 두 그룹 중 어느 그룹을 111로 둘지 바꾸면 두 증거 수열을 얻는다. 모든 엄격한 비교와 등호가 보존된다.

따라서 M<Q(N)M<Q(N)M<Q(N)이면 이 수비 전략으로 모든 질의를 처리하고 두 증거 수열을 제출할 수 있다.

채점과 복잡도 공격자 상대용 수비자는 위 전략을 쓰다가, 그룹 세 개에서 같은 상태의 두 그룹을 더 합칠 수 없게 되면 둘 사이에 엄격한 순서를 정한다. 이 시점에는 세 그룹의 값이 유일하게 정해진다. 그 전에는 위 구성으로 항상 두 수열이 존재하므로, 인터랙터는 단순 추측을 정확히 거부할 수 있다. 수비자 제출은 최종 두 증거 수열을 모든 질의 기록과 대조한다. 유효한 두 증거가 있으면 모든 중간 답변의 일관성도 보장된다.

공격 전략은 O(N)O(N)O(N) 시간과 공간을 사용한다. 수비 전략은 O((N+M)α(N))O((N+M)\alpha(N))O((N+M)α(N)) 시간, O(N)O(N)O(N) 공간을 사용한다. 인터랙터의 기록 저장은 공간이다. 모든 수치 계산은 64비트 정수 범위 안에 있다.

서브태스크 1은 가능한 모든 3N3^N3N개 수열 중 유효한 것들을 열거하고, 가능한 수열 집합을 상태로 비교 결정 트리를 메모이제이션하는 완전 탐색으로 해결한다. 상태 수는 지수적이지만 N≤6N\leq6N≤6에서는 작다. 서브태스크 2는 위 선형 크기의 전략을 사용한다.

Solution written by GPT6

LL
L
a<La<La<L
a<L<Ha<L<Ha<L<H
bbb
LLL
  • a>La>La>L이면 L<a<bL<a<bL<a<b로 가운데 값이 정해지고, 기존 HHH를 aaa와 한 번 비교하면 된다.
  • a=La=La=L이면 bbb와 HHH를 비교한다. 같으면 두 그룹에 합치고, 다르면 세 값이 모두 정해진다.
  • e−
    2
    e+1+3⌊R/2⌋+2(R mod 2)≤Q(N)e+1+3\lfloor R/2\rfloor+2(R\bmod2)\leq Q(N)e+1+3⌊R/2⌋+2(Rmod2)≤Q(N)
    O(N+M)O(N+M)
    O(N+M)