pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #371 (Div. 1) B. Searching Rectangles

http://codeforces.com/contest/713/problem/B

問題概要

(1,1)から(n,n)の領域の中に長方形が 2 つある。この長方形の座標は整数であり、2つの長方形は共通部分を持たない。

(x1,y1)から(x2,y2)の領域の中に完全に含まれている長方形の数を数えるクエリを投げることができる。200 回以内のクエリでこの 2 つの長方形の座標を特定せよ。

  • 1≦n≦216

解法

(1,1)から(x,n)までの領域に含まれる長方形の数を考えると、二分探索により長方形の右端が求められる。

f:id:pekempey:20160914151607p:plain

上下左右に対して二分探索をすることで、長方形の右端・左端・上端・下端がすべて求められるので、最後に当てはめ方 24 通りをすべて試せばいい。

正しい当てはめ方のときだけクエリの値が両方 1 になる(はず)。

codeforces だとサンプルが通らなければペナルティにならないので安心感がある。