きままにものづくり

日々の気付いたことなんかを書いてます。

SRM639Div1Easy

問題

2人で行うゲームを考える。i回戦目で勝つと2*i-1ポイントがもらえる。両者の最終的なスコア(x, y)が与えられる。xとなるスコアを得るのに必要な最小勝利回数を求めよ。与えられたスコアを満たせない場合は-1を返す。

解法

ゲームの合計のスコアはx+yとなる。n回戦まで行った時の合計のスコアは以下となる。
 \sum_i^n (2*n - 1)
 = 2*\sum_i^n n - n
 = n^2
よって、nは以下となる。
 n = \sqrt{x+y}
xが以下の値となるまで、xから2n-1を引いていく。
 1 \leq x \leq 2*n-1 \land x \neq 2
2は作れない数字なので、除外する必要がある。
xが奇数ならあと1回で、偶数なら2回でxのスコアを実現できる。

計算量

 O(\sqrt{x+y})

コード