Kazun の競プロ記録

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

AtCoder Beginner Contest 239 D問題 Prime Sum Game

AtCoder ABC ABC239 D問題 400 pts

問題

提出解答

問題の概要

高橋君と青木君が以下のゲームを行う.

高橋君は $A$ 以上 $B$ 以下の整数 $X$ を1つ選び, 青木君に伝える.
青木君は $C$ 以上 $D$ 以下の整数 $Y$ を1つ選ぶ.
$X+Y$ が素数ならば青木君の勝ち, 素数でなければ高橋君の勝ち.

両者が勝利のために最善に行動した場合, 勝者はどちらか?

制約

$1 \leq A \leq B \leq 100$
$1 \leq C \leq D \leq 100$

解法

青木君が勝つための必要十分条件は

任意の $A$ 以上 $B$ 以下の整数 $X$ に対して, $X+Y$ が素数となる $C$ 以上 $D$ 以下の整数が存在する.

である. よって, 以下のアルゴリズムによって判定できる.

の順に以下を行う.
- ${\tt flag} \gets 0$
- の順に以下を行う.
  - $X+Y$ が素数ならば ${\tt flag} \gets 1$ とする.
- ${\tt flag}=0$ ならば高橋君の勝ち
ここまでくれば青木君の勝ち

整数 $Z$ が素数かどうかを判定する方法は愚直でも $O(Z)$ で判定できる *1. よって, この問題を計算量 $O((B+D)^3)$ で求めることができた.

*1: 競技プログラミングでよく用いられる判定法は $O(\sqrt{Z})$ である.