[Codeforces] Round #534 D. Game with modulo

Game with modulo

https://codeforces.com/contest/1104/problem/D

いわゆる年齢当てゲームの一種だと思います。

考え方

題意

数字 \( a (1 \leq a \leq 10^9)\) を当てるリアクティブ問題です。

整数 \(x, y\) を質問として返ってくる答えは、

  1. \( x \mod a \leq y \mod a\)
  2. \( x \mod a > y \mod a \)

となります。この答えを元に \( a \) を当てます。また、質問の回数は \( 100 \) 回を超えてはいけません。

方針

区間の決定

\( f(x) = x \mod a \) という関数を考えると、\( k \) を整数として、\( [ak, a(k + 1) – 1] \) の区間で単調増加となります。

次に、\(x < y\) として質問をすることにします。

\( y < a \) のとき、1. が必ず成り立ちます。

一方で、2. が成り立つとき、\( a \leq y \) であるので、\( a \) の上限が分かります。どのような状況のとき\( a \) の上限が分かるかを考えます。

\( i \) 回目の質問を \( x_i, y_i \) として、\(x_1 = 0, y_1 = 1 \)、\( x_2 = 1, y_2 = 2\) とします。

区間の値を増加させて質問していったときに、初めて 2. が成り立つときが \( a \) の上限が分かります。このとき、区間に \( a \) と \( 2a\) が入らないように注意しなければなりません。

したがって、\(x_i = 2x_{i -1}, y_i = 2y_{i – 1} (i \geq 3) \) のように区間を決めればよいです。

2. が始めて成り立つ区間を \( [l, r]\) とすると、\( l < a \leq r\) が成り立ちます。

区間の二分探索

区間が求まれば、あとは二分探索を行います。この部分は年齢当てゲームと殆ど同じだと思います。二分探索については、

https://qiita.com/drken/items/97e37dd6143e33a64c8c

が分かりやすいと思います。

\( m = l + \dfrac{r – l}{2} \) として、新しい区間を \( [m, r] \) とします。このとき答えが 1. であれば区間の更新を \( r = m \) とし、そうでなければ、\( l = m \) とします。

最終的な答えが \( r \) となります。

コード

感想

コンテスト中に解法は思いついたんですが、正解には至りませんでした。区間の決め方がポイントだったと思います。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする