http://codeforces.com/contest/1019/problem/B
インタラクティブ問題。
N要素（Nは偶数）の配列Aがある。
この配列は以下のような特徴がある。
- 隠されている
- 円状である。つまり、1番目とN番目は隣接していると考える
- 隣接している要素の数はちょうど1だけ離れている
行えるクエリは2種類
質問クエリ「? i」i番目の要素の数を聞く
回答クエリ「! i」i番目の要素が答えであると答える。このクエリ後は即座に終了する必要がある
60回以下の質問でi番目の数とi+N/2番目の数が等しいようなiを答えよ。
存在しないなら-1と答える。
考察過程
1. 60回以下なので二分探索系なのは確定
2. 隣接要素はちょうど1だけ離れているというのをうまく使えないか
3. 天啓「B[i] = A[i+N/2] - A[i]」を使えばいいのでは？
4. B[i]とB[i+1]の差を考えてみると0, +2, -2のどれかになっている
5. B[i]=0であれば、答えの条件を満たす
6. しかもB[i+N/2] = -B[i]となっている
7. 中間値の定理のような雰囲気を感じる
8. これを考えるとB[i], B[i+1], ... , B[i + N/2]はB[i], B[i+1], ..., -B[i]なので中間値の定理的に答えが必ず存在しそう
9. B[i]がもともと奇数なら答えが無い（これはN/2が奇数の場合は奇数となる）
10. それ以外なら答えがあるので、中間値の定理と二分探索を使って、答えを導いていく
解法
http://codeforces.com/contest/1019/submission/41484240
答えが無い場合はN/2が奇数の場合なので、このときは除いておこう。
N/2が偶数であれば答えは必ず存在する。
B[i] = A[i+N/2] - A[i]とする。
それに伴って、質問をするときは、いつもA[i + N/2]とA[i]を聞くことにする。
diff(i) := A[i+N/2]-A[i]を返す
二分探索をする。
L=0, R=N/2が初期状態である。
するとLx = B[L], Rx = B[R] = -B[L]。
二分探索をするが、LxとRxの符号が異なるように維持しながら二分探索をしていく。
LxとRxの符号が異なるようにしていれば、その間に中間値の定理より、0となる要素の存在を維持できる。
あとは、0となる要素が出てくるまで頑張る。
int N; //--------------------------------------------------------------------------------------------------- int test = 0; int testcase[8] = { 1,2,1,2,3,4,3,2}; int ask(int i) { if (test) return testcase[i]; printf("? %d\n", i + 1); fflush(stdout); int x; cin >> x; return x; } void ans(int i) { printf("! %d\n", i + 1); fflush(stdout); } int diff(int i) { if (test) return testcase[i + N / 2] - testcase[i]; int a = ask(i); int b = ask(i + N / 2); return b - a; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; if ((N / 2) % 2 == 1) { ans(-2); return; } int L = 0, R = N / 2; int Lx = diff(L); int Rx = -Lx; if (Lx == 0) { ans(0); return; } while (L + 1 != R) { int md = (L + R) / 2; int x = diff(md); if (x == 0) { ans(md); return; } if (Lx < 0 and x < 0) { Lx = x; L = md; } else if(Rx < 0 and x < 0) { Rx = x; R = md; } else if (0 < Lx and 0 < x) { Lx = x; L = md; } else if (0 < Rx and 0 < x) { Rx = x; R = md; } } }
