AtCoderBeginnerContest239 D問題400点 「Prime Sum Game」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ A \leq B \leq 100
$ C \leq D \leq 100
気持ち
解法
よって、あとは「どうすれば高橋くんが勝てるか?」を考えればよいです。
今回のゲームでは、先に高橋くんが整数$ x(A \leq x \leq B)を決めます。
その後、青木くんが整数$ y(C \leq y \leq D)を決めます。
ここで、高橋くんは「青木くんが素数を作ってしまうこと」を「防ぎたい」です。
よって、どれかの整数$ xで「どのように青木くんが$ yを選んでも素数を作れない状況が発生した」場合、高橋くんの勝ちです。
一方で、すべての整数$ xに対して「青木くんがうまく$ yを選ぶと素数を作れる」場合は青木くんの勝ちです。
計算量
$ O(C^2)
ただし、$ Cは制約$ A, B, C, D の最大値
新たな学び
反省点
コード
code: go
func Era(n int) []bool {
dp := make([]bool, n+1)
for i := 0; i <= n; i++ {
}
for i := 2; i <= n; i++ {
for j := i * 2; j <= n; j += i {
}
}
}
return dp
}
func solve() {
era := Era(210)
var a, b, c, d int
fmt.Scan(&a, &b, &c, &d)
for x := a; x <= b; x++ {
exist := false
for y := c; y <= d; y++ {
exist = true
}
}
if !exist {
fmt.Println("Takahashi")
return
}
}
fmt.Println("Aoki")
}