---
tags: IOI
---
# IOI2010 Day1-2 熱い, 冷たい(Hotter Colder)

コーナーケースが 100 個ある二分探索

- もともと傾斜配点で、100 点を取らせる気はあんまりない
- 100 点を取るには理論下限を出さないといけない
- 連続的に考えても考察難易度が $11^+$
- そこから離散的にするときにコーナーケースが大量に発生する
- これは 1 つ 1 つ対処していくと少しずつ点数が上がるが、時間的にきびしい
- まとめて対処もできるがこれも非常に難しい
- tourist ですら 95 点　誰も満点は取れなかった

## 問題

https://oj.uz/problem/view/IOI10_hottercolder
https://www.ioi-jp.org/ioi/2010/tasks/tasks_jpn/day1/t2_hottercolder/index.html

ジルは $1$ 以上 $N$ 以下の整数を 1 つ選び、ジャックは $1$ 以上 $N$ 以下の整数を何回か聞いてその整数を当てます。
ただし、ジルは以下のように返答します。

- 最初の推測には "同じ" と答える
- 前回の推測より近ければ "熱い" と答える
- 前回の推測より遠ければ "冷たい" と答える
- それ以外なら "同じ" と答える

$\lfloor\log_2(3N)\rfloor$ 回のクエリで整数を特定してください。

## 考察

### 連続パート

$\log$ の底が $2$ なので、ほとんどの場合で区間を $1/2$ にしていく必要があります。

まず連続的に考えましょう。

対称性より、最初の 2 回は真ん中で良さそうです。
3 回目は端にすると、どちらが選ばれても条件が同じになるので端にすると良さそうです。
さて、 4 回目はどうすればいいでしょうか？

#### 区間を半分にするような場所を選ぶ


5 回目が減らせなくなります

#### 区間を $1/3$ にするような場所を選ぶ

$\log_2(\mathbf3N)$ なので、 区間を $1/3$ にするような場所を選んでみましょう。


2 回で $1/3$ にしているので、 $\log$ の底が $\sqrt3$ になってしまいます。

#### 区間を $1/4$ にするような場所を選ぶ

$\log_2(\mathbf3N)$ なので、 区間を $1:3$ に分割するような場所を選んでみましょう。


2 回で $1/4$ にしているので、 $\log$ の底が $2$ になります。
また、右のパターンでは、 2 回で $3/8$ にしかなっていませんが、端から抜け出すことができ、以降はずっと $1/2$ をすることができます。

どんな場合でも右のパターンに入るのは 1 回までなので、
$\log_2\left(\dfrac{3}{2}N\right)=\log_2(3N)-1≤\lfloor\log_2(3N)\rfloor$ 回で特定できます。

### 離散パート

さて、連続的には解けたので、離散的にしていきましょう。
注意点は以下の通りです。

#### 前回聞いた数と同じ数を聞いてはいけない

前回聞いた数と同じ数を聞いても "同じ" しか返ってきません。

#### 実際には $1/2$ ではない

返答には "熱い", "冷たい", "同じ" の 3 種類あるので、長さ 3 までなら 1 回、長さ 7 までなら 2 回、長さ 15 までなら 3 回と、約 2 倍くらいに特定できる長さが増えます。
つまり、クエリ 1 回分の余裕ができます。実はこの 1 回分を必要としている場所があって、それは最初の 1 回です。(最初の 1 回は情報が返ってこないため)

#### 実際には $1 : 3$ ではない

離散化した影響で、最適な分割位置が変わります。
$\Theta(N^4)$ の DP で実験することができて、結果はこんな感じになります。

|区間の長さ 1-N|推測すべき数|
|---|---|
|:|:|
|3|3|
|:|:|
|5|3|
|:|:|
|11|7|
|:|:|
|21|11|
|:|:|
|43|23|
|:|:|
|85|43|
|:|:|
|$\frac13(2^{n+1}+(-1)^n)$|$\frac13(2^{n+1}+(-1)^n)$|

偶数番目は $1 : 3$ になっていますが、奇数番目は $1 : 3$ よりやや中央寄りです。
省略されている部分は最適な分割位置が複数あるものです。1つ下の推測すべき数が使えます。

#### 聞いた数が区間の中央になってはいけない

|1|2|↓|4|5|6|7|
|-|-|-|-|-|-|-|
|x|o|o|o|o|o|o|

長さ 6 の区間のとき、 2 回が最適です。 しかし、区間を半分にしようと 6 を聞くと…

|1|2|3|4|5|↓|7|
|-|-|-|-|-|-|-|
|x|x|x|x|o|o|o|

これでは残り 1 回で特定できません。 6 ではなく 5 を聞く必要があります

|1|2|3|4|↓|6|7|
|-|-|-|-|-|-|-|
|x|A|A|x|B|B|B|

これはパリティを使うとうまく実装できます。

## 実装

たいへんでした。

https://oj.uz/submission/304858

#include <bits/stdc++.h>
using namespace std;
 
int Guess(int G);
 
struct T{
    map<int, int> a;
    T(){
        for(int n = 1; n < 30; n++){
            const int x = ((1 << n + 1) + (n & 1 ? -1 : 1)) / 3;
            const int y = ((1 << n) + (n & 1 ? -1 : 1) * 2) / 3 + 1;
            a[x] = y;
        }
    }
    int operator[](int x) const {
        return a.upper_bound(x)->second;
    }
} edge;
 
int HC(int N){
    if(N == 1) return 1;
    int l = 1, r = N, p = (l + r) / 2 + 1;
    Guess(p);
    bool first = 1;
    while(l < r){
        const int p2 = [&]{
            if(first){
                first = 0;
                return (l + r) / 2;
            }
            if(p == 1){
                return clamp(l * 2 - 2 + edge[r - l], 1, N);
            }
            if(p == N){
                return clamp(r * 2 - N + 1 - edge[r - l], 1, N);
            }
            int ans = clamp(l + r - p, 1, N);
            if(l <= ans && ans <= r && (r - l + 1) & 2) if(ans < p && (ans ^ l) & 1 || ans > p && (ans ^ r) & 1){
                if(N - r > l - 1) ans--;
                else ans++;
            }
            if(ans == p){
                if(N - r > l - 1) ans--;
                else ans++;
            }
            return ans;
        }();
        int ans = Guess(p2);
        if(ans == 0) return (p + p2) / 2;
        if(ans == 1){
            if(p2 < p) r = (p + p2 - 1) / 2;
            else l = (p + p2 + 2) / 2;
        }
        else{
            if(p2 < p) l = (p + p2 + 2) / 2;
            else r = (p + p2 - 1) / 2;
        }
        p = p2;
    }
    return l;
}