差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/12] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/12] – ikatakos | ||
---|---|---|---|
行 108: | 行 108: | ||
==== 解法 ==== | ==== 解法 ==== | ||
- | |||
- | 二分探索で解いたという感想が目立つが、使わなくても解ける。(汎用性は無さそう) | ||
まず、$x$ が小さい時から大きい時にどうなっていくかを考えると、上記の例を再利用して、 | まず、$x$ が小さい時から大きい時にどうなっていくかを考えると、上記の例を再利用して、 | ||
行 148: | 行 146: | ||
$x=10$ 以上では、先手が取る合計は $13-5=8$ だけ減少する。 | $x=10$ 以上では、先手が取る合計は $13-5=8$ だけ減少する。 | ||
- | 基本的にはこれを繰り返して境界と、その境界での先手の合計点を確定できる。 | + | これを繰り返して境界と、その境界での先手の合計点を確定できる。 |
ただし、どのカードが入れ替わるかに少し注意。 | ただし、どのカードが入れ替わるかに少し注意。 | ||
行 166: | 行 164: | ||
最後まで残ったクエリは、$x=21$の様に完全に交互になる。 | 最後まで残ったクエリは、$x=21$の様に完全に交互になる。 | ||
+ | ソートせずに、境界を事前計算しておいてクエリ毎に二分探索でもよいが、多分Pythonだと遅い。 | ||
<sxh python> | <sxh python> |