DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

Yet Another Stone Game

問題に戻る

解説

후공이 이기는 상태를 패배 상태라고 하자. OOO를 홀수인 돌 더미의 개수, MMM을 모든 돌 더미 크기의 최솟값이라고 하자.

가능한 KKK는 N−2N-2N−2, N−1N-1N−1, NNN뿐이다. 단, N=3N=3N=3, K=1K=1K=1인 경우는 따로 처리한다.

K=1K=1K=1인 경우

한 번 행동할 때마다 전체 돌의 수가 정확히 111 감소한다. 따라서 게임의 전체 행동 횟수는 ∑Ai\sum A_i∑Ai​로 고정된다. 이 합이 짝수일 때만 패배 상태이다.

K=NK=NK=N인 경우

모든 돌 더미가 짝수인 상태가 정확히 패배 상태이다. 이 상태에서 한 번 행동하면 적어도 하나의 더미가 홀수가 된다. 반대로 홀수인 더미가 하나라도 있으면 홀수인 더미를 전부 골라 모든 더미를 짝수로 만들 수 있다.

K=N−1K=N-1K=N−1인 경우

모든 더미의 홀짝이 같은 상태가 정확히 패배 상태이다. 모든 더미가 짝수이거나 모든 더미가 홀수인 상태에서 111개 이상 N−1N-1N−1개 이하의 더미를 고르면 두 홀짝이 섞인다. 반대로 두 홀짝이 섞인 상태에서는 홀수인 더미를 전부 골라 모든 더미를 짝수로 만들 수 있다.

K=N−2K=N-2K=N−2인 경우

이 경우에는 N≥4N\geq4N≥4이다. 다음 두 종류가 정확히 패배 상태이다.

  • 모든 더미가 짝수이다.
  • 홀수인 더미가 N−1N-1N−1개이고, 유일한 짝수 더미의 크기가 전체의 최솟값이다.

첫 번째 상태에서 행동하면 홀수인 더미가 111개 이상 N−2N-2N−2개 이하가 되므로 두 패배 상태 중 어느 것도 될 수 없다.

두 번째 상태에서 모든 더미를 짝수로 만들려면 N−1N-1N−1개의 홀수 더미를 모두 골라야 하므로 불가능하다. 같은 종류의 상태로 이동하려면 유일한 짝수 더미와 홀수 더미 하나를 함께 골라야 한다. 그러면 기존의 최솟값이 111 감소하여 홀수가 되고, 새로 짝수가 된 더미보다 작아진다. 따라서 새 유일한 짝수 더미가 최솟값일 수 없다. 즉, 패배 상태에서 다른 패배 상태로 이동할 수 없다.

이제 위 두 종류가 아닌 상태에서 패배 상태로 이동할 수 있음을 보이자.

  • 홀수 더미가 111개 이상 N−2N-2N−2개 이하라면, 홀수 더미를 모두 골라 모든 더미를 짝수로 만든다.
  • 모든 더미가 홀수라면, 최솟값인 더미 하나를 골라 유일한 짝수이자 최솟값으로 만든다.
  • 홀수 더미가 N−1N-1N−1개이지만 유일한 짝수 더미가 최솟값이 아니라면, 그 짝수 더미와 최솟값인 홀수 더미를 고른다. 그러면 후자가 유일한 짝수이자 최솟값이 된다.

따라서 각 테스트 케이스에서 OOO, MMM, 돌의 합만 계산하면 된다. 시간 복잡도는 O(N)O(N)O(N)이고, 추가 공간 복잡도는 O(1)O(1)O(1)이다.

Solution written by GPT6