この小課題では query の呼び出し回数に制限はなく、送っていいデータも 1 000 050 ビットまでと、迷路の情報と太郎の位置をそのまま送信しても十分な大きさである。どのような方法を使っても良いだろう。
ここでは小課題 1 に比べて、送ってもいいデータの大きさが半分程度になっている。迷路の情報を半分程度の大きさに圧縮することができればよいが、そのためには迷路の構造に着目する必要がある。
問題文に書かれているように、迷路は全域木をもとにして作られている。したがって、全域木の頂点にあたる部分は常に通路であることがわかっている。具体的には、 i を 2 で割ったあまりと j を 2 で割ったあまりが等しいとき、M[i][j] の値はすぐにわかる。よってマップの状態を送信するとき、そのようなマスについては情報を送らなくても良い。さらに外壁の情報もおくる必要がないことから、送信するデータの大きさを半分未満にすることができる。
また、別解として 20 ビットを送信するだけでよい解法もある。これは query を呼び出しながら幅優先探索を行って現在位置を求めることで、迷路の情報を送る必要がなくなることを利用している。
この小課題から query の呼び出し回数に制限が加わる。すなわち、効率良く現在位置を求める必要がある。
ここではそのために二分探索を用いることを考える。たとえば、現在位置から右に X マス進むとはじめて迷路の外側に出るような X を二分探索で求めよう。このとき、単純に query(0, X) の戻り値からではそのマスが迷路の内側か外側かを判定できないことに注意する必要がある。
あるマスが迷路の内部かどうかを決定するために、小課題 2 でも利用した迷路の構造をふたたび利用しよう。利用した性質は i % 2 = j % 2 ならば M[i][j] の値は確定しているということだった。ここでは特に i, j がともに奇数のとき必ず M[i][j] = 0 であることを利用する。上から y+1 番目、左から x+1 番目のマスを (x, y) と表すことにしよう。すると (x, y) が迷路の内部であるなら、(x, y), (x+1, y), (x, y+1), (x+1, y+1) の 4 つのマスのうち少なくとも 1 つは通路である。これを使って、あるマスが迷路の内部かどうかを決定できる。
この方法での query の呼び出し回数を考えよう。1 つのマスが迷路の内部かどうかを決定するのに最大 4 回の呼び出しが必要である。また、二分探索は ceil(log2(1000)) = 10 回の繰り返しが必要である。したがって一回の二分探索に最大 40 回の呼び出しが必要である。全体でこの二分探索を 4 回行う必要があるので、合計で 160 回以下の呼び出しで太郎と次郎双方の現在位置が求められる。これは小課題 3 を解くのに十分である。
この小課題はさらに厳しく、120 回の query 呼び出しで現在位置を求める必要がある。
小課題 3 を解くのに用いた二分探索を改善して呼び出し回数を 40 回以上減らすことを考えよう。現在位置 (x, y) を求めるのに、まず 1 回小課題 3 と同様の二分探索を行って x の値を決定したとする。つぎに y の値を決定するとき、x の値はすでにわかっており、その偶奇も当然わかっていることから、調べる必要のあるマスを減らすことができる。すなわち x が偶数ならば (x+1, Y), (x+1, Y+1) の 2 マス、奇数ならば (x, Y), (x, Y+1) の 2 マスを調べるだけで十分である。
この改善によって 4 回の二分探索のうち 2 回で呼び出し回数を削減できる。1 つのマスが迷路の内部かどうか決定するのに最大 2 回で十分になるので、合計で (40 + 20) * 2 = 120 回の呼び出しで太郎と次郎双方の現在位置が求められる。これは小課題 4 を解くのに十分である。
この小課題で満点を得るためには 80 回の query 呼び出しで現在位置を求めなければならない。
この小課題を解くためにも先ほどまでと同じ性質「i, j がともに奇数ならば M[i][j] = 0」を用いる。まず、現在位置 (x, y) について x, y がともに奇数の場合を考えよう(このようなマスを
さて、今回は現在位置 (x, y) について x, y の偶奇はわかっていないので、上の方法をそのまま用いることはできない。ただし、x, y がともに偶数であることはないということには注意する必要がある(x, y がともに偶数なら M[y][x] = 1 でなければならない)。現在位置は通路であり、かつ迷路は木構造(連結)であるから、現在位置と辺を共有する 4 近傍のマスのうち少なくとも 1 つはまた通路である。このような通路マスのうち 1 つを選ぶ(通路マスが 4 近傍に複数ある場合はどれでもよい)。すると、x, y がともに偶数であることはないため、現在位置か 4 近傍の通路マスのうちどちらかは必ず奇数マスである。
現在位置と近傍の通路マスのうちどちらかが奇数マスであることは分かったが、どちらが奇数マスであるかはわからない。そこで、上に述べた二分探索をその両方のマスから行なって、それぞれ m, m' という値が得られたとする。どちらかが奇数マスであることから m, m' のうち片方は正しい値であるが、もう片方はそうではない。ここで、正しくない値は正しい値よりも大きくなることはないということを用いる。なぜなら、奇数マスでないところから行った二分探索ではより近い位置で壁に当たることはあっても、迷路の外側で通路にあたることはありえないからである。したがって、正しい値として max(m, m') を採用すればよい。
この方法での query の呼び出し回数を見積もろう。まず 4 近傍のうちの通路マスを探すために最大 4 回の呼び出しが必要である。1 回の二分探索では (x + 2*m, y) について考えるので m の範囲は 0 ≦ m ≦ W/2 を考えればよい。さらに、あるマスが迷路の内部かを判定するためには 1 回の呼び出しでよいので、1回の二分探索では最大 ceil(log2(1000 / 2)) = 9 回の呼び出しが行われる。この二分探索は x を決めるのに 2 回、y を決めるのにも 2 回行われるので、全体では最大 4 + 4 * 9 = 40 回の呼び出しが必要である。これを太郎と次郎の双方について行うので 40 * 2 = 80 回となり、満点が得られる。