Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 244 C問題 Yamanote Line Game

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

インタラクティブ問題
自分とコンピュータで以下のゲームを行う.

  • 自分から交互に  1 以上  2N+1 以下の整数のうち, まだ宣言していない整数を  1 つ宣言する. 先に宣言できなくなったほうが負け.

このゲームにおいて, うまく行動することにより, 自分が勝つことができる. 実際にこのゲームを行い, 勝て.

制約

  •  1 \leq N \leq 1000

解法

例えば, 自分の番において, まだ宣言されていない整数のうち, 最小の整数を答え続ければ良い. この方法は愚直にでも  O(N^2) で求めることができる.