2013年の目標振返り

もうそろそろ７月か。

2013年も半分終わり。ということで、年始に立てた目標がどれだけ実現できたのかを振返り、後半をどのように過ごすか考えてみたいと思います。

年始に立てた目標はこんな感じでした。

１つずつ振り返って行きますか。

1. 週に4話英語の漫画を読む

これは余裕で達成できてますね。100点です。この調子で続けたいです。

2. 「めぞん一刻」英語版アニメを全話見る

これもいい感じです。100点。オープニングテーマが『陽だまり』に変わる回くらいまでみました。そろそろ終盤です。このくらいのスピードのラフな感じの英語でもだいぶ聞き取れるようになりました。

3. ESL PODのビハインド分（1年半分くらい）をきちんとやる

これは遅れ気味です。60点。目標立てたのは3月ですが、1月時点では2年分くらいビハインド分がありました。今年の分もやると考えると3年分やることになるのですが、正直難しいです。1日で1週間分の教材をこなす日もありましたが、集中力が持続せず逆効果という感じでした。
『年末までに2013年3月分までの教材を終わらせる。』という目標に変えようと思います。
ESP PODにはすごく助けられましたが、現時点ではレベルがあってないような気がするので（スピードが遅くて眠くなることがしばしば。。）来年は別の教材を探す必要があるかもしれません。

4. 土日でその週に行われたCodeforcesの問題をすべて(div2のみ)解く

40点くらい。31コンテスト中13コンテストのみ問題を解きました。
すべての問題を理解できるようにしようとすると、今の実力では1コンテスト1日くらいかかってしまいます。週に1回時間が取れるか取れないかくらいな感じなので、現実的な目標じゃなかったかもしれません。
あと、これは趣味なのでノルマを課してやるべきものじゃなくて、時間のあるときにやるくらいのスタンスの方がいいのかなと考えたりもします。
とりあえず、後期は『毎週1コンテスト分の問題をすべて解く』という目標で頑張りたいと思います。

C++でk-d tree実装

　C++でk-d treeを実装してみた。k-d treeのアイディアはシンプルで簡単に言うと二分探索木のk次元空間拡張バージョン。もうちょっと詳しく言うと、

1. 節点の高さごとに軸を選んで、軸と交わる超平面でk次元空間を二つに分割する。
2. 1.で選んだ超平面より左にあるデータは左部分木に、右にあるデータは右部分木に格納していく。
3. データ集合の中央値を通るように1.の超平面を選ぶことで、平衡二分探索木にすることができる。

これを使うと、nearest neighborで最近傍を見つけるときの計算を高速化することができる。
詳しく知りたいひとは、ここ。

問題

とりあえずソースコードを書く前にk-d treeを用いると高速に解くことができそうな問題を考えてみた。

『二次元平面上にN個の点が与えられる。その後L個の点が与えられる。L個の点それぞれについて、先に与えられたN個の点のうちどれに最も近いのかを求めよ。』

straightforwardな解法

普通に書くとこうです。

#include <iostream>
#include <vector>

using namespace std;

int N, L;

inline double dist(double x1, double y1, double x2, double y2) {
    return (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
}

int main() {
    cin >> N;
    vector<double> xs(N), ys(N);
    for (int i = 0; i < N; i++)
        cin >> xs[i] >> ys[i];
    cin >> L;
    for (int i = 0; i < L; i++) {
        double x, y;
        cin >> x >> y;
        double best = 1e100;
        int nearest = -1;
        for (int j = 0; j < N; j++) {
            if (dist(x, y, xs[j], ys[j]) < best) {
                best = dist(x, y, xs[j], ys[j]);
                nearest = j;
            }
        }
        cout << nearest << endl;
    }

    return 0;
}

k-d treeを用いた解法

k-d treeを使うとこんな感じ。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, L;

inline double dist(double x1, double y1, double x2, double y2) {
    return (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
}

struct data {
    int index;
    vector<double> v;
    data(int _d) : v(_d) {}
    data() {}
};

struct vertex {
    data val;
    vertex *left;
    vertex *right;
};

class axisSorter {
    int k;
public:
    axisSorter(int _k) : k(_k) {}
    double operator()(const data &a, const data &b) {
        return a.v[k] < b.v[k];
    }
};

vertex *makeKDTree(vector<data> &xs, int l, int r, int depth) {
    if (l >= r)
        return NULL;

    sort(xs.begin() + l, xs.begin() + r, axisSorter(depth % xs[0].v.size()));
    int mid = (l+r)>>1;

    vertex *v = new vertex();
    v->val = xs[mid];
    v->left = makeKDTree(xs, l, mid, depth+1);
    v->right = makeKDTree(xs, mid+1, r, depth+1);

    return v;
}

inline double dist(const data &x, const data &y) {
    double ret = 0;
    for (int i = 0; i < (int)x.v.size(); i++)
        ret += (x.v[i] - y.v[i]) * (x.v[i] - y.v[i]);
    return ret;
}

inline double sq(double x) {
    return x*x;
}

data query(data &a, vertex *v, int depth) {
    int k = depth % a.v.size();
    if ((v->left != NULL && a.v[k] < v->val.v[k]) || 
        (v->left != NULL && v->right == NULL)) {
        data d = query(a, v->left, depth+1);
        if (dist(v->val, a) < dist(d, a))
            d = v->val;
        if (v->right != NULL && sq(a.v[k] - v->val.v[k]) < dist(d, a)) {
            data d2 = query(a, v->right, depth+1);
            if (dist(d2, a) < dist(d, a))
                d = d2;
        }
        return d;
    }
    else if (v->right != NULL) {
        data d = query(a, v->right, depth+1);
        if (dist(v->val, a) < dist(d, a))
            d = v->val;
        if (v->left != NULL && sq(a.v[k] - v->val.v[k]) < dist(d, a)) {
            data d2 = query(a, v->left, depth+1);
            if (dist(d2, a) < dist(d, a))
                d = d2;
        }
        return d;
    }
    else
        return v->val;
}

int main() {
    cin >> N;

    vector<data> xs(N, data(2));
    for (int i = 0; i < N; i++) {
        xs[i].index = i;
        cin >> xs[i].v[0] >> xs[i].v[1];
    }

    vertex *root = makeKDTree(xs, 0, N, 0);

    cin >> L;
    for (int i = 0; i < L; i++) {
        data a(2);
        cin >> a.v[0] >> a.v[1];
        data nearest = query(a, root, 0);
        cout << nearest.index << endl;
    }

    return 0;
}

速度比較

N=1,000,000、L=100,000とすると、straightforward解は240秒弱。対してk-d treeを使った解法は8秒くらい。30倍くらい速い。もうちょっと真面目にコードを書けばさらに10倍くらいは速くできると思う。（多分）

JUnitを使って単体テストをする(2)

　djUnitを使って遊んでみました。djUnitとは、JUnitの拡張版みたいなもので、

• coverage report
• virtual mock object

といった便利な機能を提供してくれるテストフレームワークです。

coverage reportはその名のとおり、テストのカバレッジを可視化してくれる機能です。テスト対象のソースで実行されていない行にマーカーを表示してくれます。

virtual mock objectは、メソッドの戻り値を自由に設定することでテスト用のモックを作成せずともテストができるという素晴らしい機能です。

具体的な使用方法は、以下のサンプルを見てください。

想定

Serviceクラスの単体テストをしたい。Serviceクラスは外部システムから情報を取得していて、取得した情報によって挙動が変わる。
単体テストなので、実際に外部システムには接続せずにテスト用のモックを使って動作確認をしたい。

まずテスト対象のServiceクラスです。doSomething()メソッドのテストを行うこととします。

package com.kenjih.main;

public class Service {
 public String doSomething() throws NumberFormatException {
  UserInfo userInfo = ExternalSystemLib.getUserInfo();
  
  if (userInfo == null)
   return "User Info is null.";  
  if (userInfo.getAge() < 0)
   throw new NumberFormatException();
  if (userInfo.getTel().startsWith("090"))
   return "Mobile phone number is registered.";
  
  return "His/Her name is " + userInfo.getName() + ".";
 }
}

以下がユーザー情報を格納するBeanです。

package com.kenjih.main;

public class UserInfo {
 private String name;
 private String tel;
 int age;
 
 public int getAge() {
  return age;
 }
 public void setAge(int age) {
  this.age = age;
 }
 public String getName() {
  return name;
 }
 public void setName(String name) {
  this.name = name;
 }
 public String getTel() {
  return tel;
 }
 public void setTel(String tel) {
  this.tel = tel;
 }
}

次に、外部システムと通信を行ってユーザー情報を取得する機能。

package com.kenjih.main;

public class ExternalSystemLib {
 public static UserInfo getUserInfo() {
  UserInfo userInfo = new UserInfo();
  
  //　実際は外部システムと通信をしてユーザー情報を取得するという想定。
  
  return userInfo;
 }
}

djUnitを使ったテスト

ExternalSystemLibMockのようなモックは作成せずともテストができます。仮想モックオブジェクトの機能を利用してテストを行います。

package test.kenjih.com;

import static org.junit.Assert.*;
import jp.co.dgic.testing.common.virtualmock.MockObjectManager;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import com.kenjih.main.ExternalSystemLib;
import com.kenjih.main.Service;
import com.kenjih.main.UserInfo;

public class TestService {

 Service service = new Service();
 
 @Before
 public void setUp() throws Exception {
  MockObjectManager.initialize();
 }

 @After
 public void tearDown() throws Exception {
 }

 @Test
 public void testDoSomething_1() {
  MockObjectManager.addReturnNull(ExternalSystemLib.class, "getUserInfo");
  
  assertEquals("User Info is null.", service.doSomething());
 }

 @Test(expected = NumberFormatException.class)
 public void testDoSomething_2() {
  UserInfo userInfo = new UserInfo();
  userInfo.setAge(-10);
  MockObjectManager.addReturnValue(ExternalSystemLib.class, "getUserInfo", userInfo);
  
  service.doSomething();
 }

 @Test
 public void testDoSomething_3() {
  UserInfo userInfo = new UserInfo();
  userInfo.setAge(20);
  userInfo.setName("Taro");
  userInfo.setTel("123456789");
  MockObjectManager.addReturnValue(ExternalSystemLib.class, "getUserInfo", userInfo);
  
  assertEquals("His/Her name is Taro.", service.doSomething());
 }

}

ポイントは、

• MockObjectManager.addReturnNull(クラス, メソッド名); で指定したクラスのメソッドが必ずnullを返すように設定できる。
• MockObjectManager.addReturnValue(クラス, メソッド名, 値); で指定したクラスのメソッドが必ず指定した値を返すように設定できる。

というところです。他にもいろいろ便利な機能があります。

実行結果

Eclipseでテスト実行した結果です。

テストで実行されていない行にマーカーが設定されます。

また、カバレッジの情報を外部ファイルにExportする機能もあります。

サマリーレポートも一緒にExportしてくれます。

いやー、便利ですね。

JUnitを使って単体テストをする(1)

　適当にテストして遊んでみた。

まず、適当なクラスを作ります。コイツをテスト対象として使います。

package com.kenjih.main;

public class DumbCalculator {
 public int multiply(int x, int y) {
  int ret = 0;
  for (int i = 0; i < y; i++)
   ret += x;
  return ret;
 }
 
 public int pow(int x, int y) {
  int ret = 1;
  for (int i = 0; i < y; i++)
   ret *= x;
  return ret;
 }
 
 public int divide(int x, int y) {
  return x / y;
 }
}

テストクラスは以下のとおり。

package com.kenjih.test;

import static org.junit.Assert.*;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import com.kenjih.main.DumbCalculator;

public class TestDumbCalculator {
 
 DumbCalculator calculator;
 
 @Before
 // テスト実行前に呼ばれる
 public void setUp() throws Exception {
  calculator = new DumbCalculator();
 }

 @After
 // テスト完了後に呼ばれる
 public void tearDown() throws Exception {
 }

 @Test
 public void testMultiply() {
  assertEquals(1000, calculator.multiply(10, 100));
 }

 @Test
 public void testPow_1() {
  assertEquals(10000000000L, calculator.pow(10, 10));
 }

 @Test(timeout = 10)
 // 10ミリ秒以内に処理が完了するか？
 public void testPow_2() {
  calculator.pow(10, 10000000);
 }
 
 @Test (expected = ArithmeticException.class)
 // ArithmeticExceptionをスローするか？
 public void testDivide() {
  calculator.divide(10, 0);
 }
}

Eclipseでテスト実行した結果。

JUnit便利ですねー。

次回はdjUnitを使って、virtual mock objectとかcoverage reportとかやってみようかと思います。

Convex Hull TrickでDequeからPop Backするときの条件

Convex Hull TrickでDequeからPop Backするときの条件についてちょっと気になったので、考えてみました。

まずConvex Hull Trickについてですが、ここに詳しい解説があります。

要は、「y_i = a_i * x + b_iという直線集合が与えられて、あるx（複数のxが与えられる）についてy_iが最小になるiを求めよ。というクエリーを効率よく求めるためのトリックで、その応用としてDPの計算を高速化する際にも利用できることがありますよ。」
というもの。

下の3問を解いてみると、どんな感じか感覚がつかめると思います。いずれもConvex Hull Trickに気づくとDequeを使って計算量を落とすことができます。

• K-Anonymous Sequence (POJ 3709)
• Cats Transport (Codeforces Round #185)
• Land Acquisition (Usaco Mar 08 Gold)

（K-Anonymous Sequenceは蟻本にも載ってます。恐るべし、蟻本。）

で、何が気になったかというと、Dequeから直線L2をpop_backする条件です。

L1 : y = a_1 * x + b_1

L2 : y = a_2 * x + b_2

L3 : y = a_3 * b + b_3

として、今L3をDequeに入れようとしているとします。

このときL2がもう不要だといえる条件は、「L1とL3の交点 <= L1とL2の交点」です。

L1とL2の交点は、(b_2 - b_1) / (a_1 - a_2)です。L1とL3の交点は、(b_3 - b_1) / (a_1 - a_3)です。よって、

(b_2 - b_1) * (a_1 - a_3) >= (b_3 - b_1) * (a_1 - a_2)

です。

気になったのは、a_1 - a_2 = 0のときとa_1 - a_3 = 0のとき。交点がない（または直線が完全に一致する）けど、上の条件で足りているのか？

場合分けして考えてみました。

i)  a_1 = a_2のとき

(b_2 - b_1) * (a_1 - a_3) >= 0ならL2は不要となります。

a_1 >= a_3なので、b_2 >= b_1のとき不要ということになります。これは直線L2が完全にL1より上の時不要ということなので、正しいです。

ii) a_1 = a_3のとき

a_1 >= a_2 >= a_3なので、a_1 = a_2 = a_3となります。

このときは、(b_2 - b_1) * 0 >= (b_3 - b_1) * 0のときL2が不要となりますが、この条件は常になりたつので、L2は常に不要となります。これは正しい条件でしょうか？

今すでにDequeに入っているL1とL2の状態について考えてみます。L2の方がL1より下にある（またはL1とL2が一致）とすれば、L2を入れる時点でL1は消去されているはずです。ということは、L2の方がL1より上にあるということになり、常にL2はDequeから取り除いて良いということになります。

よってii)の場合も条件(b_2 - b_1) * (a_1 - a_3) >= (b_3 - b_1) * (a_1 - a_2)で足りているということになります。

そういえば今旬の「今でしょっ！」の人が、
「日常生活で、『よし、今日は直線の交点求めるか！』なんていう人がいたらヤバい」みたいなこと言ってたけど、趣味で直線の交点求めて喜ぶ人は少なからずいると思います。

on one's knees

Eric ClaptonのLaylaのlyricsがおもしろい。今までギターの演奏の方に集中していて歌詞を聞けていなかった。。

Layla, you've got me on my knees.
Layla, I'm begging, darling please.
Layla, darling won't you ease my worried mind.

"on one's knees"はイディオムで以下の意味があるらしい。

1. 文字通り膝を地面に付けること
2. とても残念な様子を表す
3. 誰かに助けてもらいたい様子を表す
4. とても弱っている状態を表す

今回は、3.の意味でしょうね。愛しのレイラさんに跪いてお願いしている男の様子が目に浮かびます。

Octaveで画像処理（2）

Octave使うと、FFTが簡単に使えます。もちろん二次元配列に対するFFTも簡単にできます。
ということで、ハイパスフィルターを作ってみました。

function test2()
  [img, _, _] = imread("~/programming/octave/fft/test1a.png");
  [H, _, _] = imread("~/programming/octave/fft/filter.png");
  
  F = fft2(img);
  for i = 1:512
    for j = 1:512
      F(i, j) = H(i, j) * F(i, j);
    end
  end
  
  T = ifft2(F);
  T = abs(T);
  T = T / max(max(T)) * 255;
  T = uint8(T);

  imwrite(T, "~/programming/octave/fft/test1b.png");

endfunction

いまいちうまく書けてないです。特に二重でforループまわしているところは遅いです。うまい書き方あったら教えてください。

画像は以下を使用。

で、以下がフィルタ。どうもフィルタの形が重要なようで四隅を切り取ったような感じにしないとうまくフィルタリングができませんでした。真ん中の部分が高周波だからといって、単純に真ん中に円を書いてそこだけ通過させるようなものを書いてもうまくいきませんでした。このあたりは理由がよく分かっていないので勉強が必要です。

そして、ハイパスフィルターをかけた画像が以下！
おおっ。。ちょっと感動しました。

ついでに前回つくったgrayscaleの画像もハイパスってみました。白黒反転した方がよさそうかな。それは次回のテーマということで。

There is nothing to fear but fear itself

When watching an English dubbed anime, I encountered an expression, like, "There is nothing to fear but fear itself." At first it didn't make sense to me.

So I went over to the internet and looked up its meaning. I learned that the phrase was a quote from inaugural address of Franklin D. Roosevelt. Technically speaking, it was used by Francis Bacon a few hundred years before his speech.

Kind of hard to interpret it, but I think it means "if you think there is something to fear, there it comes. But if you think there is nothing to fear, it never comes up."

Talk about a cheer-up quote. I've got to remember it.

Octaveで画像処理（１）

Octaveを使うと画像<->配列の変換が簡単にできるのでいろいろ遊んでみようと思います。

まずは画像を読み込んで、grayscaleに変換して書き込むということをやってみました。

function test1()
  [img, map, alpha] = imread("~/programming/octave/fft/lena.jpg");
  monotone = img(:,:,1)/3 + img(:,:,2)/3 + img(:,:,3)/3;
  imwrite(monotone, "~/programming/octave/fft/img1.jpg");
endfunction

　１行目で画像lena.jpgを読み込みます。imgに各ピクセルのRGB値が格納されます。画像サイズがn*mなら、imgはn*m*3の三次元配列になります。
　2行目でRGBの平均を計算します。
　3行目で画像ファイルにmonotoneの情報を書き込んでいます。この例では、第一引数はn*mの二次元配列ですが、フルカラーの情報をファイルに書き込みたい場合は、第一引数をn*m*3の三次元行列にすることもできます。

実行は以下のようにします。（ここでは上のプログラムを~/programming/octave/fft/test1.mに保存しているとします。）

octave> addpath("~/programming/octave/fft");
octave> test1

以下が実行結果。

Google Code Jam 2013 Round 2

Code JamのRound 2がありました。

惜しくもGoogleに認められた世界レベルのプログラマーだけが着用することを許されたTシャツを手に入れられるか入れられないかギリギリのラインで終わってしまいました。

去年もGoogleに認められた世界レベルのプログラマーだけが着用することを許されたTシャツラインにぎりぎり届かないくらいの順位でしたが、ルール違反とかで上の人が数十人ほどいなくなって、なんとかGoogleに認められた世界レベルのプログラマーだけが着用することを許されたTシャツを手に入れることができました。

なので、今年もGoogleに認められた世界レベルのプログラマーだけが着用することを許されたTシャツを手に入れられる可能性はまだ残っているわけです。

本番終了後、二分探索の上限の初期値をnとすべきところを(n+1)としていたのが発覚して、もしそれがなかったらGoogleに認められた世界レベルのプログラマーだけが着用することができるTシャツを確実に手に入れられてたと思うと残念でなりません。
それどころかこのミスがなければ、Round 3行けてたみたいです。いやー、悔しい。

ただ今回のCode JamでRound 3行きがもはや手の届かないレベルじゃ無くなったというのが分かったので、来年はRound 3進出を目標にしようと思います。

復習のため、A, B, CをJavaで解いてみました。Dは解ける気がしないので放置。

Ticket Swapping

損失が最大になるように乗客を降ろす = 後で乗ってきた人を先に降ろす（降りるべき人が後で乗ってきた人のチケットを使って降りる）が成り立つことに気づけばstackを使って解けます。LIFOです。

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import java.io.*;
import java.util.*;

@SuppressWarnings("unused")
public class Main {
	static final long MOD = 1000002013;
	Scanner sc = new Scanner(System.in);
	
	long cost(long x, long y, long n, long p) {
		long ret = (y - x) * (n + n - y + x + 1) / 2 % MOD;
		ret = ret * p % MOD;
		return ret;
	}
	
	void solve() {
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] s = new int[M];
		int[] t = new int[M];
		int[] p = new int[M];
		int[] q = new int[M];
		
		for (int i = 0; i < M; i++) {
			s[i] = sc.nextInt();
			t[i] = sc.nextInt();
			p[i] = sc.nextInt();
			q[i] = p[i];
		}
		
		Set<Integer> stations = new TreeSet<Integer>();
		for (int i = 0; i < M; i++) {
			stations.add(s[i]);
			stations.add(t[i]);
		}
		
		long ret = 0;
		// legal ride
		for (int i = 0; i < M; i++) {
			ret += cost(s[i], t[i], N, p[i]);
			ret %= MOD;
		}
		
		// illegal ride
		int[] stack = new int[2*M];
		int size = 0;
		
		for (int k : stations) {
			// get on the train
			for (int i = 0; i < M; i++) {
				if (s[i] == k)
					stack[size++] = i;
			}
			
			// get off the train
			long cnt = 0;
			for (int i = 0; i < M; i++) {
				if (t[i] == k)
					cnt += q[i];
			}
			
			while (cnt > 0) {
				int x = stack[--size];
				if (cnt >= p[x]) {
					ret -= cost(s[x], k, N, p[x]);
					ret = (ret % MOD + MOD) % MOD;
					cnt -= p[x];
					p[x] = 0;
				} else {
					ret -= cost(s[x], k, N, cnt);				
					ret = (ret % MOD + MOD) % MOD;
					stack[size++] = x;
					p[x] -= cnt;
					cnt = 0;
				}				
			}
		}
		
		System.out.println(ret);
	}

	void run() {
		int T = sc.nextInt();
		for (int id = 1; id <= T; id++) {
			System.out.printf("Case #%d: ", id);
			System.err.printf("Solving Case #%d...\n", id);
			solve();
			System.out.flush();
		}
	}

	void debug(Object... os) {
		System.err.println(deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Many Prizes

• 賞品が必ずもらえる。
• 賞品をもらえる可能性がある。

のどちらも再帰的に判定できます。また、関数がmonotonicなので二分探索が使えます。

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.math.BigInteger.*;
import java.io.*;
import java.util.*;

@SuppressWarnings("unused")
public class Main {
	Scanner sc = new Scanner(System.in);

	boolean shouldWin(long n, long p, long x) {
		if (p <= 0) return false;
		if (n <= p) return true;
		if (x == 0) return true;
		return shouldWin(n/2, p-n/2, (x-1)/2);
	}
	
	boolean canWin(long n, long p, long x) {
		if (p <= 0) return false;
		if (n <= p) return true;
		if (x == 0) return true;
		if (x == n-1) return canWin(n/2, p-n/2, n/2-1);
		else return canWin(n/2, p, (x+1)/2);
	}
	
	void solve() {
		long N = sc.nextLong();
		long P = sc.nextLong();
		
		N = 1L<<N;
		
		long x = 0;
		long y = N-1;
		
		long lo = 0;
		long hi = N;
		
		while (hi - lo > 1) {
			long mid = (lo + hi) >> 1;
			if (shouldWin(N, P, mid))
				lo = mid;
			else
				hi = mid;
		}
		x = lo;
		
		lo = 0;
		hi = N;
		while (hi - lo > 1) {
			long mid = (lo + hi) >> 1;
			if (canWin(N, P, mid))
				lo = mid;
			else
				hi = mid;
		}
		y = lo;
		
		System.out.println(x + " " + y);
	}

	void run() {
		int T = sc.nextInt();
		for (int id = 1; id <= T; id++) {
			System.out.printf("Case #%d: ", id);
			System.err.printf("Solving Case #%d...\n", id);
			solve();
			System.out.flush();
		}
	}

	void debug(Object... os) {
		System.err.println(deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Erdős–Szekeres

問題の導入がおもしろいです。

「整数[1,N]のpermutationは最低でも長さsqrt(N)の部分増加列または部分現象列を持つ。」らしいです。

なぜそうなるか簡単に考えてみました。

まずすべてのi, j, i < jについて(A[i], B[i])と(A[j], B[j])は必ず異なることを示します。
X[i] < X[j]ならA[i] < A[j]です。
また、X[i] > X[j]ならB[i] > B[j]となります。よってすべてのi, j, i < jについて(A[i], B[i]) , (A[j], B[j])は異なります。

あとは鳩ノ巣原理を使えば、すべてのiについてA[i] < sqrt(N)かつB[i] < sqrt(N)であれば矛盾することがわかるので、A[i] >= sqrt(N)またB[i] >= sqrt(N)となるようなiが存在することが分かります。

話が脱線しましたが、問題自体は

1. A, Bのリストからトポロジカル順序を求める
2. ワーシャルフロイドで推移閉包を求める
3. トポロジカル順序に矛盾しないようにかつなるべく辞書順が最小になるように数字をあてはめていく

というふうな感じで解けます。wataさんのコードがわかりやすいです。