Problem - B - Codeforces

概要

以下のクエリを $60$ 回まで投げることで、整数 $a$ の値を特定せよ。

各クエリでは、 $0 \leq x, y \leq 2 \times 10^9$ を満たす好きな整数 $x, y$ を投げる。 すると $(x \bmod a) \lt (y \bmod a)$ なら y 、そうでなければ x が返ってくる。

制約

• $1 \leq a \leq 10^9$

考察

前半

$a$ が $x$ と比べて小さすぎる場合、 $x \bmod{a}$ から得られる情報は少ない。 逆に、以下のようなケースは使えそうである。

• $x \lt a$ のとき、 $x \bmod{a} = x$ 。
• $a \leq x \lt 2a$ のとき、 $x \bmod{a} = x - a$ 。

ここから、 $2^p \lt a \leq 2^{p+1}$ を満たす整数 $p$ について、以下が成り立つ。

$$ (2^0 \bmod{a}) \lt (2^1 \bmod{a}) \lt \cdots \lt (2^p \bmod{a}) \gt (2^{p+1} \bmod{a}) $$

これを利用すると、 $\log a$ 回以下のクエリで $p$ を求められる。具体的には、 $i$ 回目(0-indexed)のクエリで $(x, y) = (2^{i}, 2^{i + 1})$ を投げ、 x が帰ってきたら $p = i$ が確定する。

なお、 $a = 1$ の場合はこのような $p$ は存在しない。しかしこのケースは、最初に $(x, y) = (0, 1)$ のクエリを投げることで判定できる。

後半

$2^p \lt a \leq 2^{p+1}$ を満たす $p$ が見つかったので、後はこの中のどこに $a$ があるかを求めればいい。

まず、この区間内で以下が成り立つ。

$$ (2^p \bmod{a}) \lt (2^p + 1 \bmod{a}) \lt \cdots \lt (a - 1 \bmod{a}) \gt (a \bmod{a}) \lt \cdots \lt (2^{p + 1} \bmod{a}) $$

さらに $(2^{p + 1} \bmod{a}) = 2^{p + 1} - a \lt 2^{p + 1} - 2^p = 2^p = (2^p \bmod{a})$ より、 $\gt$ より後ろは全て $(2^p \bmod{a})$ より小さい。

以上より、以下が成り立つ。

• $2^p \lt y \lt a$ のとき、 $(2^p, y)$ のクエリの結果は y となる。
• $a \leq y \leq 2^{p + 1}$ のとき、 $(2^p, y)$ のクエリの結果は x となる。

よって $(2^p, y)$ のクエリの結果が x となる最小の $y$ が $a$ となる。そのような $y$ は、二分探索によって $p$ 回で求められる。

実装例

一番外のループは非本質なので省いた。

Submission #171320230 - Codeforces

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>

using namespace std;

void answer(int x) {
  cout << "! " << x << endl;
}

bool y_is_larger(int x, int y) {
  cout << "? " << x << " " << y << endl;

  char res;
  cin >> res;
  if (res == 'e') exit(0);
  return res == 'y';
}

void solve() {
  // a=1 を弾く
  if (!y_is_larger(0, 1)) {
    answer(1);
    return;
  }

  int p = 0;
  while (y_is_larger(1 << p, 1 << (p + 1))) ++p;

  // a in (l, r]
  int l = (1 << p), r = (1 << (p + 1));
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (y_is_larger(1 << p, mid)) {
      l = mid;
    } else {
      r = mid;
    }
  }

  answer(r);
}