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

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

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

트로미노 게임

문제로 돌아가기

해설

칸 수가 짝수이면 codex가 직전 빨간 칸을 180180180도 회전한 칸을 고른다. 고정된 칸이 없어 항상 가능하다. 게임이 끝나면 회전이 빨간 배치와 파란 배치를 일대일로 대응시키므로 동점이다. 한 변이 111이면 일렬로 (1,2),(3,4),…(1,2),(3,4),\ldots(1,2),(3,4),…를 짝짓고, 홀수 길이라면 마지막 칸을 남긴다. codex는 직전 칸의 짝이 비어 있으면 그 칸을 고르고, 아니면 아무 빈 칸을 고른다. 모든 짝에 파란 칸이 하나 이상 생긴다. 연속한 세 칸은 반드시 완전한 짝을 포함하므로 빨간 트로미노는 없다. 따라서 codex가 이긴다. 나머지 경우에는 두 변이 모두 333 이상의 홀수이다. coxld는 중앙을 고른 뒤 상대의 수를 180180180도 회전하여 응수한다. 중앙을 포함하지 않는 빨간 배치와 파란 배치는 회전으로 대응한다. 중앙 상하좌우 네 칸은 마주 보는 두 칸의 색이 반대이므로 빨간 두 칸은 중앙을 기준으로 서로 수직인 방향에 있다. 이 두 칸과 중앙이 빨간 ㄱ자 트로미노를 이루어 coxld가 이긴다. 서브태스크 1은 삼진 상태로 각 칸을 기록하고 미니맥스 탐색한다. 배치 수를 KKK라 하면 시간 O(3RC(RC+K))O(3^{RC}(RC+K))O(3RC(RC+K)), 공간 O(3RC+K)O(3^{RC}+K)O(3RC+K)이다. 전체 풀이는 케이스당 시간 O(1)O(1)O(1), 추가 공간 O(1)O(1)O(1)이다. 트로미노 배치는 최대 6RC≤6⋅1066RC\le6\cdot10^66RC≤6⋅106개이고 면적 곱셈은 64비트로 계산한다. Solution written by GPT6.1