Hatena::ブログ(Diary)

TopCoderとJ言語と時々F# このページをアンテナに追加 RSSフィード

2012-03-14

[]受験記

東京大学理科一類を受験しました

時系列

2011/7

IOI楽しいナ〜

2011/8上

堕落

2011/8下

しょうがないので倫理をやる

2011/9

センター模試で化学6割とか物理7割とかとる

2011/10

まだ n ヶ月あるしどうとでもなるでしょ……

2011/11

倫理すっかり忘れてしまった

2011/12上

あれ,これ実はやばいのでは?

2011/12下

学校が企画した冬季勉強合宿みたいなのへ行く

センター形式の問題で化学6割とかとる

2012/1上

家でゆっくり理科のセンター過去問をやる

化学7割とかとる

センター試験

神が降りてきて848/900点とる

2012/1下

まだ1ヶ月ぐらいあるしどうとでもなるでしょ……

2012/2上

堕落

GCJJオフ会楽しかったナ〜

2012/2中(2次試験2週間前ぐらい)

あれ,これ実はやばいのでは?

2012/2中(2次試験1週間前ぐらい)

過去問をやる

数学何回やっても4完できないし理科は物理で100分以上使う

2次試験

数学4完できないし理科は物理で100分以上使う

(練習でできなかったことが本番で出来るわけないという当たり前のことを実感する)

2012/2下

IIDXやりたい

2012/3上

卒業式めんどくさい

2012/3/10(合格発表)

受かっていた

今では立派な受験余裕でした勢です

SP1級受かったよ〜

感想

直前の対策でなんとかなりすぎだと思う.

僕が言えたことではないけど,もうちょっと直前の対策だけではどうにもならないような入試問題にするべきなのでは…….

それはいいとして,僕が受験成功したのは本当に神のおかげなのではないだろうか.「神はいると思いますか?」「僕についています」みたいな感じだった.

ところで今回の受験で悔やむところはふたつほどあって,ひとつは僕がダメすぎるということ.頭では分かっているのに堕落しすぎだし,ちゃんと勉強してれば本物の受験余裕勢にもなれただろうに.

もうひとつは合格してしまったので,IOI日本代表は受験に失敗しないという悪しき風習を破ることができなかったこと.誰か,受験に成功しつつこの悪習を打ち破る方法を考えて実践してほしい.

まあ,最終的な感想として一切反省していないようなことを言うけど,終わりよければ全てよしですよネ.

今後

IIDX頑張ります!!!!!!!!

あとICPCも頑張ります.

2011-07-23

[][]IOI 2011 Day 2

  • Day 1 夜
  • 寝るはずがIOI過去問を読んだりしていて遅くなる
  • 死ぬように眠りについた
  • Day 2 朝
  • なんとか起床するが眠すぎて死ぬ
  • 目を覚ますために合成数を切断して素数を叩くゲームをやる
  • とりあえずがんばって朝ごはんを食べにいく
  • 朝ごはんはバイキングのようなアレだった
  • ハム類が豊富に用意されていたのですべて2つずつとったら皿がハムだけになった
  • ごはんは美味しいけどホテルのメシっぽい感じが漂っていた
  • タイ料理を食べてみたい
  • 9時からは開会式
  • よく寝ました(ごめんなさい)
  • ほんとうにずっと寝ていた気がするので内容をあまり覚えていない
  • 人が何かのオーラをまとったり,よくわからないものと戦闘を繰り広げているあたりで目が覚めた
  • 国紹介のときには眠気がすっかり飛んでいたので大きく手をふっておいた
  • おひるごはん
  • チキンの入ったカレーのような何かがタイっぽくて嬉しかった
  • デザートにアイスクリームがあったが,苺味がなかったので女子力は上がらなかった
  • ひとつのカップにチョコとバニラのアイスを両方入れてくれと言っている人がいた
  • ふつうにうまかった
  • その後は Practice Session
  • 所持品に関する規定がなんか厳しくなっているようで困惑する
  • とりあえず上から羽織れるものと筆記用具を預けた
  • Practiceは特にやることもなかった
  • ひと通り問題を解いたあとパソコンの画面いっぱいに「/\_/\」と表示しておいた
  • ところ,ドイツの人にいじられて「<(^-^)>」こういうものになっていた(日本の顔文字が好きらしい)
  • ので,さらにいじって「\(^o^)/」に変えた
  • そしてそのドイツの人と「\(^o^)/」このポーズで一緒に写真を撮った
  • さらにその後で「/\_/\ < fox!」としておいた
  • ところ,ドイツの人に free the fish というGNOMEイースター・エッグを走らされた
  • 小さな魚が画面に現れて「/\_/\ < fox!」を横断していくシュールな光景が繰り広げられた
  • Practice後はFree Time
  • このFree Timeが終わるあたりで選手とリーダーたちの接触が禁止される時間がくる
  • ので,インターネットもできなくなる(できるかもしれないがやらないことが推奨される)
  • そうすると死んでしまうので,その前にネカフェに来る
  • そこでblogなどを書く

2010-08-10

[][]IOI 2008 Egypt過去問 PYRAMID BASE

問題概要

横M、縦Nの二次元フィールドに辺がx軸y軸とそれぞれ平行な長方形の障害物がP個ある。i個目の障害物はCiの金で撤去可能であり、与えられた予算はBである。このフィールド上にできるだけ広い正方形の土地を確保せよ。

  • 1 <= M <= 1,000,000
  • 1 <= N <= 1,000,000
  • 1 <= Ci <= 7,000

次の3つのテストグループがある。

35点分
  • B = 0 (障害物は撤去できない)
  • P <= 1,000
35点分
  • 0 < B <= 2,000,000,000
  • P <= 30,000
30点分
  • B = 0 (障害物は撤去できない)
  • P <= 400,000

解法

まず最初に共通の性質として、答となる最大の正方形の辺は必ずどれかの長方形に接している。よって長方形に接するところだけを調べれば良い、というのが基本。

2つ目の35点分の解法

つまり障害物を撤去できるとき。基本的には正方形の一辺の長さについて二分探索を行う。ある長さ L の正方形がフィールド上に確保できるかどうかを現実的な時間で判定できればこのケースは解けることになる。

答となる正方形の辺が長方形に接することを利用すると、全ての長方形について、それに接する一辺の長さ L の正方形を置いたときに、その正方形と重なる長方形を撤去するためのコストが B 以下ならばよい。しかし、これをそのまま実装すると時間がかかりすぎる。

そこでまず問題を変形する。長さ L の正方形をフィールド上にそのまま確保するのではなくて、全ての長方形の横の長さを左に、縦の長さを下に、それぞれ L だけ伸ばしたフィールド上において一辺の長さが 1 の正方形を確保すると考える。(このときの一辺の長さが 1 の正方形は、目的とする一辺の長さ L の正方形の左下端になっている)

するとこの問題は次のようにして解ける。最初に要素数 N の配列 S を用意し、全要素を 0 で初期化する。そして走査線を左から右に走らせつつ、次の操作を行う。

  • 走査線が長方形の左端に達した場合、その長方形の下y座標(y1とする)から上y座標(y2とする)まで、S[y1..y2] にそれぞれこの長方形を撤去するためのコスト(cとする)を加算する。
  • 走査線が長方形の右端に達した場合、S[y1..y2] からそれぞれ c を引く。
  • いずれの場合でも、上記の2操作が終わった後に S[1..N-L+1] から最小の要素を見つける。その最小の要素の値が B 以下であれば、フィールド上に一辺の長さ L の正方形を確保することは可能であると判定する。そうでない場合は走査を続ける。

これをそのまま実装すると当然遅いので、Sをsegment treeで実装してやれば一回の操作(範囲に対する加算、減算、最小値)はそれぞれ O(log N) で済む。また、走査線は長方形の左右両端のみに興味があるので、そこだけ操作するようにすればこの判定は全体で O(P log N) で動く。

あとはこれを使って二分探索をするだけで、その範囲は 1 から min(M, N) までなので、全体の計算量は O(P log N log min(M, N)) となる。segment treeの実装は慣れていれば優しいし、他の実装も軽めなので辛くはない。

1つ目の35点分および3つ目の30点分の解法

つまり障害物を撤去できないとき。ここで考えるのは、「正方形の左端のx座標を固定したとき、とりうる最大の右端のx座標は何か?」ということである。この値が左端のx座標について広義単調増加であることから、次のアルゴリズムを開発できる。

最初に要素数 N の配列 S を用意し、全要素を 0 で初期化する。また、答となる値を sol とし、最初は0にしておく。そして走査線を2本、左から右に走らせつつ、次の操作を行う。ここで2本の走査線のうち1本は、上記の問における「左端のx座標」に対応し(左走査線とする)、もう1本は「とりうる最大の右端のx座標」に対応する(右走査線とする)。

  • 右走査線が長方形の左端に達した場合、S[y1..y2] にそれぞれ(正の値ならなんでもよいが) 1 を加算する。
  • 左走査線が長方形の右端に達した場合、S[y1..y2] からそれぞれ 1 を引く。
  • いずれの場合でも、min(右走査線のx座標 - 左走査線のx座標, S[1..N]の中で0が連続する最大の区間の長さ)と sol を比較し、その値がsolより多ければ sol をその値にする。

ここで「右走査線のx座標 - 左走査線のx座標」がその時にとりうる正方形の一辺の最大の長さの上界になってることは言うまでもないとして、「S[1..N]の中で0が連続する最大の区間の長さ」というのが「走査線に挟まれた部分において、左走査線から右走査線までの間に、障害物が占めるマスがひとつもないようなy座標が連続する最大の長さ」であることを考えれば、これで最適解が出せることに納得がいくはずである。

この場合もそのままの実装では当然遅いので、Sをsegment treeで実装してやれば一回の操作が O(log N) で済む。この走査も同じく長方形の両端だけを走査するので時間計算量は全体で O(P log N) である。

実装に関しては、segment treeの実装はそこまで難しくない(とはいっても、やや応用的な範囲になるのかな?)。ただ走査の部分が(少なくとも僕は)バグバグでどうしようもなく手間取った。まあこれは単に僕がSweep-line系のアルゴリズムの実装が死ぬほど苦手だというだけかもしれない。


ソース

MacBook Pro上のVirtual BoxにIOI2010の競技環境を作った上で、最大ケースが4秒ちょっとぐらい。時間制限は5秒になってるけど、本番に間に合うかどうかは非常に怪しいのでもっと賢い実装が必要かも。そもそもいくら走査の実装が苦手だからといってもあまりにもひどいと思う……。

segtree, solveB0 が B = 0 のときの解法で、 segtree2, solve が B > 0 のときの解法。

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct segtree {
  struct seg {
    int add;
    int zleft, zright, zmax;
  } *S;
  int n;
  void init(int x, int l, int r) {
    S[x].add = 0;
    S[x].zleft = S[x].zright = S[x].zmax = r-l;
    if(r-l <= 1) return;
    int mid = (l+r)/2;
    init(x*2, l, mid);
    init(x*2+1, mid, r);
  }
  segtree(int siz) {
    n = siz;
    S = new seg[4*siz+50];
    init(1, 1, siz+1);
  }
  inline int get_r(int x, int cl, int cr, int l, int r) {
    if(r-l <= 0 || S[x].add > 0) return 0;
    return min(S[x].zright, cr-l);
  }
  inline int get_l(int x, int cl, int cr, int l, int r) {
    if(r-l <= 0 || S[x].add > 0) return 0;
    return min(S[x].zleft, r-cl);
  }
  int query(int x, int cl, int cr, int l, int r, int psum) {
    if(r-l <= 0) return 0;
    if(psum+S[x].add > 0) return 0;
    if(cl == l && cr == r) return psum == 0 ? S[x].zmax : 0;
    int ret = 0, mid = (cl+cr)/2;
    if(r<=mid) {
      ret = query(2*x, cl, mid, l, r, psum+S[x].add);
    } else if(mid<=l) {
      ret = query(2*x+1, mid, cr, l, r, psum+S[x].add);
    } else {
      ret = query(2*x, cl, mid, l, mid, psum+S[x].add);
      ret = max(ret, query(2*x+1, mid, cr, mid, r, psum+S[x].add));
      ret = max(ret, get_r(2*x, cl, mid, l, mid) + get_l(2*x+1, mid, cr, mid, r));
    }
    return ret;
  }
  int query(int l, int r) {
    return query(1, 1, n+1, l, r, 0);
  }
  void incr(int x, int cl, int cr, int l, int r, int v, int psum) {
    int mid = (cl+cr)/2;
    if(cl == l && cr == r) {
      S[x].add += v;
      if(S[x].add > 0) S[x].zleft = S[x].zright = S[x].zmax = 0;
      else {
        if(r-l == 1) S[x].zleft = S[x].zright = S[x].zmax = 1;
        else {
          S[x].zleft = get_l(2*x, cl, mid, cl, mid);
          if(S[x].zleft == mid-cl) S[x].zleft += get_l(2*x+1, mid, cr, mid, cr);
          S[x].zright = get_r(2*x+1, mid, cr, mid, cr);
          if(S[x].zright == cr-mid) S[x].zright += get_r(2*x, cl, mid, cl, mid);
          S[x].zmax = max(S[2*x].zmax, S[2*x+1].zmax);
          S[x].zmax = max(S[x].zmax, get_r(2*x, cl, mid, cl, mid) + get_l(2*x+1, mid, cr, mid, cr));
        }
      }
      return;
    }
    if(l<mid) incr(2*x, cl, mid, l, min(r, mid), v, psum+S[x].add);
    if(mid<r) incr(2*x+1, mid, cr, max(l, mid), r, v, psum+S[x].add);
    if(S[x].add > 0) {
      S[x].zleft = S[x].zright = S[x].zmax = 0;
      return;
    }
    S[x].zleft = get_l(2*x, cl, mid, cl, mid);
    if(S[x].zleft == mid-cl) S[x].zleft += get_l(2*x+1, mid, cr, mid, cr);
    S[x].zright = get_r(2*x+1, mid, cr, mid, cr);
    if(S[x].zright == cr-mid) S[x].zright += get_r(2*x, cl, mid, cl, mid);
    S[x].zmax = max(S[2*x].zmax, S[2*x+1].zmax);
    S[x].zmax = max(S[x].zmax, get_r(2*x, cl, mid, cl, mid) + get_l(2*x+1, mid, cr, mid, cr));  
  }
  void insert(int l, int r) {
    incr(1, 1, n+1, l, r, 1, 0);
  }
  void remove(int l, int r) {
    incr(1, 1, n+1, l, r, -1, 0);
  }
};

struct side {
  int x, cost;
  int y1, y2;
  bool start;
  side(int a, int b, int c, int d=0, bool e=false)
    : x(a), y1(b), y2(c), cost(d), start(e) { }
};
struct side_cmp {
  bool operator ()(const side& a, const side& b) {
    return a.x == b.x ? a.y1 < b.y1 : a.x < b.x;
  }
};
struct side_cmp_b {
  bool operator ()(const side& a, const side& b) {
    return a.x == b.x ? (a.start != b.start ? b.start : false) : a.x < b.x;
  }
};
int solveB0(int M, int N, int P,
            vector<int> x1, vector<int> y1, 
            vector<int> x2, vector<int> y2, vector<int> c)
{
  vector<side> E1, E2;
  for(int i=0; i<P; ++i) {
    E1.push_back(side(x1[i], y1[i], y2[i]));
    E2.push_back(side(x2[i], y1[i], y2[i]));
  }
  E1.push_back(side(N+1, 1000000000, 1));
  E2.push_back(side(1, -1000000000, 1));
  sort(E1.begin(), E1.end(), side_cmp());
  sort(E2.begin(), E2.end(), side_cmp());
  int left = 0, right = 0, sol = 0;
  segtree S(M);
  while(right < E1.size()) {
    int ptr;
    bool fail = false;
    while(right < E1.size()) {
      sol = max(sol, min(E1[right].x-E2[left].x, S.query(1, M+1)));
      ptr = right;
      if(S.query(1, M+1) < E1[right].x-E2[left].x) {  
        fail = true;
        break;
      }
      while(ptr < E1.size() && E1[right].x==E1[ptr].x) {
        if(E1[ptr].x <= N) { 
          S.insert(E1[ptr].y1, E1[ptr].y2);
        }
        ptr++;
      }
      if(S.query(1, M+1) < E1[right].x-E2[left].x) {
        fail = true;
        break;
      }
      right = ptr;
      if(right >= E1.size()) break;
      sol = max(sol, min(E1[right].x-E2[left].x, S.query(1, M+1)));
    }
    if(right >= E1.size()) break;
    sol = max(sol, min(E1[right].x-E2[left].x, S.query(1, M+1)));
    if(fail) {
      while(left+1 < E2.size() && S.query(1, M+1) < E1[right].x-E2[left].x) {
        int ptr2 = left+1;
        while(ptr2 < E2.size() && E2[left+1].x == E2[ptr2].x) {
          if(ptr2 > 0) {
            S.remove(E2[ptr2].y1, E2[ptr2].y2);
          }
          ptr2++;      
        }
        left = ptr2-1;
        fail = false;
      }
      for(int p=right; p<ptr; ++p)
        S.remove(E1[p].y1, E1[p].y2);
      ptr = right;
    }
    right = ptr;
    sol = max(sol, min(E1[right].x-E2[left].x, S.query(1, M+1)));
    if(N+1-E2[left].x <= sol) break;
  }
  return min(sol, min(M, N));
}

struct segtree2 {
  struct seg {
    int val, add;
  } *S;
  int n;
  void init(int x, int l, int r) {
    S[x].val = S[x].add = 0;
    if(r-l <= 1) return;
    int mid = (l+r)/2;
    init(2*x, l, mid);
    init(2*x+1, mid, r);
  }
  segtree2(int siz) {
    n = siz;
    S = new seg[4*n+50];
    init(1, 1, n+1);
  }
  ~segtree2() { delete[] S; }
  void incr(int x, int cl, int cr, int l, int r, int v) {
    if(cl == l && cr == r) {
      S[x].add += v;
      return;
    }
    int mid = (cl+cr)/2;
    if(l<mid) incr(2*x, cl, mid, l, min(mid, r), v);
    if(mid<r) incr(2*x+1, mid, cr, max(mid, l), r, v);
    S[x].val = min(S[2*x].val+S[2*x].add, S[2*x+1].val+S[2*x+1].add);
  }
  void incr(int l, int r, int v) {
    incr(1, 1, n+1, l, r, v);
  }
  int query(int x, int cl, int cr, int l, int r) {
    if(cl == l && cr == r) {
      return S[x].val + S[x].add;
    }
    int mid = (cl+cr)/2;
    if(r<=mid) {
      return query(2*x, cl, mid, l, r) + S[x].add;
    } else if(mid<=l) {
      return query(2*x+1, mid, cr, l, r) + S[x].add;
    } else {
      return min(query(2*x, cl, mid, l, mid), query(2*x+1, mid, cr, mid, r)) + S[x].add;
    }
  }
  int query(int l, int r) {
    return query(1, 1, n+1, l, r);
  }
};

bool check(int M, int N, int B, int L, int P,
           vector<int> x1, vector<int> y1, 
           vector<int> x2, vector<int> y2, vector<int> c)
{
  segtree2 S(M);
  vector<side> E;
  for(int i=0; i<P; ++i) {
    x1[i] = max(1, x1[i]-L+1);
    y1[i] = max(1, y1[i]-L+1);
  }
  for(int i=0; i<P; ++i) {
    E.push_back(side(x1[i], y1[i], y2[i], c[i], true));
    E.push_back(side(x2[i], y1[i], y2[i], -c[i], false));
  }
  E.push_back(side(1, -1, -1, true));
  E.push_back(side(N+1-L, -1, -1, false));
  sort(E.begin(), E.end(), side_cmp_b());
  for(int i=0; i<E.size(); ) {
    int p;
    if(E[i].x > N+1-L) break;
    for(p=i; p<E.size() && E[i].x==E[p].x; ++p) 
      if(E[p].y1 >= 1)
        S.incr(E[p].y1, E[p].y2, E[p].cost);
    i = p;
    if(S.query(1, M-L+2) <= B) return true;
  }
  return false;
}

int solve(int M, int N, int B, int P,
          vector<int> x1, vector<int> y1, 
          vector<int> x2, vector<int> y2, vector<int> c)
{
  int lo = 1, hi = min(M, N);
  if(!check(M, N, B, lo, P, x1, y1, x2, y2, c)) return 0;
  while(hi-lo>1) {
    int mid = (hi+lo)/2;
    if(check(M, N, B, mid, P, x1, y1, x2, y2, c))
      lo = mid;
    else
      hi = mid;
  }
  if(check(M, N, B, hi, P, x1, y1, x2, y2, c)) return hi;
  return lo;
}

int main()
{
  int M, N, B, P;
  scanf("%d%d%d%d", &N, &M, &B, &P);
  vector<int> x1(P), y1(P), x2(P), y2(P), c(P);
  for(int i=0; i<P; ++i) {
    scanf("%d%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i], &c[i]);
    x2[i]++; y2[i]++;
  }
  if(B == 0) printf("%d\n", solveB0(M, N, P, x1, y1, x2, y2, c));
  else printf("%d\n", solve(M, N, B, P, x1, y1, x2, y2, c));
  return 0;
}

2010-06-21

[][]IOI 2008 Egypt過去問 TELEPORTERS

問題概要

数直線上にいくつかの点のペアが存在し、その片方に乗るともう片方に飛ばされるように(テレポートするように)なっている。全ての点の座標は1以上で2,000,000以下。同じ座標に複数の点は存在しない。

この数直線上で0から出発し、どんどん右へ進んで行く。最終的に座標2,000,001に達した時点でテレポートした回数が得点として得られる。

はじめにあるN個のペアの座標が与えられるので、そこにM個以下の新たなペアを追加して、獲得できる得点を最大化せよ。はじめに与えられるN個のペアの座標は整数だが、新たに追加するペアの座標は0より大きく2,000,001より小さい任意の実数で構わない。

  • 1 <= N <= 1,000,000
  • 1 <= M <= 1,000,000

解法

座標が出てくるが、実際は点同士の左右の関係だけが必要なことや、点から点へ移るということからグラフに落とせそうな感じがする。しかし普通に点をそのまま頂点としてペアを辺で結んでも何ら嬉しいことはないので工夫が必要。

そこで、2N個の点によって分けられる2N+1個の区間を頂点とし、ある区間から出る辺はその区間の右端点からテレポートした先の点を左端点とする区間へのものとする。そうするとそのグラフは1本の経路と複数(0個かもしれない)のサイクルからなることがわかる。

新たなペアを付け加えるとこのグラフに何が起きるかを観察すると次のようなパターンがあることがわかる。

  • 同じ連結成分に属する「同じ」区間にそれぞれ新たな点を置くと、その連結成分の辺数が1本増え、さらに1本の辺からなるサイクルが1つ新たに生まれる。
  • 同じ連結成分に属する2つの「異なる」区間にそれぞれ新たな点を置くと、その2つの区間の間の辺がすべてスキップされる。
  • 違う連結成分に属する2つの区間にそれぞれ新たな点を置くと、その2つの連結成分が合体する。

すると最初のケースでは獲得できる得点が1増え、2番目のケースではその2つの区間の間の辺の数-1だけ得点が減り、3番目のケースでは新たに合体する連結成分の辺の数+2だけ得点が増える。

よって基本的には3番目のケースになるように新たにペアを加えていけばよいが、そのうち連結成分が全て合体して1つになってしまう。そうなったら今度は最初のケースのように新たにペアを加え、その結果できた辺数1のサイクルを3番目のケースを使ってまた合体させるということを繰り返せば良い。


ソース

これも微妙に1秒が切れない。死ぬ。ソースは変数使い回しまくりで汚物。

#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

int W[1000000], E[1000000];
int P[2000050], T[2000050], C[2000050];
int X[2000050], S[2000050];

int main()
{
  int N, M;
  scanf("%d%d", &N, &M);
  for(int i=0; i<N; ++i)
    scanf("%d%d", &W[i], &E[i]);
  for(int i=0; i<N; ++i)
    P[i] = W[i];
  for(int i=0; i<N; ++i)
    P[i+N] = E[i];
  for(int i=0; i<N<<1; ++i)
    T[P[i]]++;
  int pos = 0;
  for(int i=0; i<=2000000; ++i)
    if(T[i])
      P[i] = pos++;
  for(int i=0; i<N; ++i) {
    W[i] = P[W[i]];
    E[i] = P[E[i]];
    T[W[i]] = E[i]+1; C[E[i]+1] = W[i];
    T[E[i]] = W[i]+1; C[W[i]+1] = E[i];
  }
  T[2*N] = -1; C[0] = -1;
  int components = 0, sol;
  for(int i=0; i<=2*N; ++i) {
    if(X[i] == 0) {
      queue<int> que;
      int cnt = 1;
      X[i] = 1;
      que.push(i);
      while(!que.empty()) {
	int v = que.front(); que.pop();
	if(T[v] != -1 && X[T[v]] == 0) {
	  X[T[v]] = 1;
	  cnt++;
	  que.push(T[v]);
	}
	if(C[v] != -1 && X[C[v]] == 0) {
	  X[C[v]] = 1;
	  cnt++;
	  que.push(C[v]);
	}
      }
      if(i == 0) sol = cnt-1;
      else S[components++] = cnt;
    }
  }
  memset(T, 0, sizeof(T));
  pos = 0;
  for(int i=0; i<components; ++i)
    T[S[i]]++;
  for(int i=1; i<=2000000; ++i)
    for(int j=0; j<T[i]; ++j)
      S[pos++] = i;
  while(M > 0 && components > 0) {
    sol += S[--components] + 2;
    M--;
  }
  if(M > 0) {
    sol += M / 2 + M / 2 * 3;
    if(M % 2 == 1) sol++;
  }
  printf("%d\n", sol);
  return 0;
}

[][]IOI 2008 Egypt過去問 LINEAR GARDEN

問題概要

LとPのみからなるN文字の文字列であり、どの連続した区間をとっても一方の文字が他方の文字より3文字以上多いことがないという制約を満たす文字列がひとつ与えられる。与えられた文字列が、この制約を満たす文字列のうち辞書順で何番目かを求めよ。mod Mで。

  • 1 <= N <= 1,000,000
  • 7 <= M <= 10,000,000

解法

文字列について、次のように走査することを考える。

  • はじめ、カウンタを0に設定しておく
  • 文字Lが現れたらカウンタをインクリメント
  • 文字Pが現れたらカウンタをデクリメント

すると、条件を満たす文字列はカウンタの最大値と最小値の差が2以下におさまる。これを利用する。

dp[i][lo][hi][cnt] := i文字目までが決定している文字列で、そこまで走査したときのカウンタの最小値がlo、最大値がhi、現在の値がcntであるような状況において、ここから先、文字数がNになるようにLとPを付け加えてできる「条件を満たす」文字列の数

とおいてDPするとよい。lo, hi, cnt はそれぞれ-2以上2以下なので5通りの値をとり、iはN通りの値をとるから N*5*5*5 = 125N もの部分問題ができるのでDPでよくあるメモリ節約テクニックを使う。実行時間については、lo, hi, cnt は125通りの組み合わせがあるが、そのうちhi-lo <= 2 であり lo <= cnt <= hi であるものは少ないので問題ない。

最終的な答を求めるには、例えばサンプルにある "PLPPL" なら、 "PLPL?", "PLL??", "L????" (?は任意の文字)に対応する状態のDP表の値を全て合計すればよい。


ソース

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

struct state {
  int lo, hi, now;
};
char S[1<<20];
state T[1<<20];

int main()
{
  int N, MOD;
  int dp[2][7][7][7] = {{{{0}}}};
  scanf("%d%d", &N, &MOD);
  scanf("%s", S);
  T[0].lo = T[0].hi = T[0].now = 3;
  if(S[0] == 'L') T[0].lo = T[0].now = 2;
  else T[0].hi = T[0].now = 4;
  for(int i=1; i<N; ++i) {
    if(S[i] == 'L') {
      T[i].now = T[i-1].now-1;
      T[i].lo = min(T[i-1].lo, T[i].now);
      T[i].hi = T[i-1].hi;
    } else {
      T[i].now = T[i-1].now+1;
      T[i].lo = T[i-1].lo;
      T[i].hi = max(T[i-1].hi, T[i].now);
    }
  }
  for(int i=1; i<=3; ++i)
    for(int j=3; j<=i+2; ++j)
      for(int k=i; k<=j; ++k)
	dp[0][i][j][k] = 1;
  int sol = 0;
  for(int i=1; i<=N; ++i) {
    int p = i&1, q = 1-p;
    if(S[N-i] == 'P') {
      int lo = min(T[N-i].lo, T[N-i].now-2);
      int hi = i == N ? 3 : T[N-i-1].hi;
      int now = T[N-i].now-2;
      sol = (sol + dp[q][lo][hi][now]) % MOD;
    }
    for(int lo=1; lo<=3; ++lo) {
      for(int hi=3; hi<=lo+2; ++hi) {
	for(int now=lo; now<=hi; ++now) {
	  dp[p][lo][hi][now] = 0;
	  if(now+1-lo <= 2) // P 
	    dp[p][lo][hi][now] = (dp[p][lo][hi][now] + dp[q][lo][max(hi, now+1)][now+1]) % MOD;
	  if(hi-now+1 <= 2)  // L
	    dp[p][lo][hi][now] = (dp[p][lo][hi][now] + dp[q][min(lo, now-1)][hi][now-1]) % MOD;
	}
      }
    }
  }
  printf("%d\n", (sol+1)%MOD);
  return 0;
}

[][]IOI 2008 Egypt過去問 ISLANDS

問題概要

N個の頂点とN個の辺を持ち、どの頂点も最低1つの辺で接続されているような重み付き無向グラフが与えられる。好きな頂点から出発して、次のどちらかの移動を繰り返す。ただし同じ頂点に2度訪れることはできない。

  • 辺を辿って移動する。
  • どのように辺を辿っても移動できないような頂点にワープする。

このとき、通った辺の重みの和を最大化せよ。

  • 2 <= N <= 1,000,000
  • 1 <= 辺重み <= 100,000,000

解法

まず問題は連結成分ごとに分解できるので、連結成分ごとに最大重みの経路を求める問題を解いてすべて合計すればよい。

ここでグラフに課せられた制約(孤立点が存在しない)から、全ての連結成分は頂点数と辺数が等しい。よってこの連結成分は木に1本だけ辺を追加した形をしている。見方を変えれば、この連結成分にはサイクルが1つだけ存在する。

さて、このサイクルについて考えたい。サイクルの頂点を (v[1], v[2], ..., v[c]) として、ある頂点 v[k] に注目する。v[k] から v[k-1] と v[k+1] への辺を切ると、そこには v[k] を根とする木が残る。つまりサイクルは c 個の根付き木の根同士が繋がってできたものと見なすことができる。

このことから最適解は、次のいずれかになる。

  • サイクルの頂点のうちどれかを根とする木の直径
  • サイクルのある2頂点 s, t を根とする木の高さと、サイクル中における s, t の距離の和

後者のイメージとしては、 s を根とする木の葉から根である s へと辿り、そこからサイクルを s から t へ辿り、最後に t からその木の葉まで辿るという感じになる。

あとは、後者の方を計算するときに愚直に実装するとサイクルの頂点数を c とすれば O(c^2) 時間が必要になってしまうので注意が必要。v[k]を根とする木の高さを height[k] として、v[1]からv[2], v[3], ... と辿ってv[k]まで到達する時の距離を len[k]、そしてサイクル中の辺重みの総和を L とすると後者は

max(i < j) { height[i] + height[j] + max(v[j]-v[i], L-(v[j]-v[i])) }

を計算することで求められるがこの式を変形して

max {
  max(i < j) { height[i] + height[j] + v[j] - v[i] },
  L + max(i < j) { height[i] + height[j] - v[j] + v[i] }
}

とし、さらに

max {
  max(i < j) { (height[i] - v[i]) + (height[j] + v[j]) },
  L + max(i < j) { (height[i] + v[i]) + (height[j] - v[j]) }
}

と考えればi, jが分離できたので O(c) で計算可能になる。

以上を全てまとめると、全て頂点数について線形時間なので全体で O(N)。


ソース

という以上の解法を実装したけど2秒が切れない。 isl19g.in あたりで3秒ちょっとかかってしまう。実装が下手すぎる模様。

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct edge {
  int src, dst, len, id;
  edge(int s, int d, int l, int i)
    : src(s), dst(d), len(l), id(i) { }
};
typedef vector<edge> vertex;
typedef vector<vertex> graph;

void get_cc_dfs(const graph& g, int v, vector<int>& ids, int k)
{
  if(ids[v] >= 0) return;
  ids[v] = k;
  for(int i=0; i<g[v].size(); ++i)
    get_cc_dfs(g, g[v][i].dst, ids, k);
}

vector<graph> get_connected_components(const graph& g)
{
  const int n = g.size();
  vector<graph> ret;
  vector<int> ids(n, -1);
  for(int i=0; i<n; ++i) ids[i] = -1;
  int cnt = 0;
  for(int i=0; i<n; ++i)
    if(ids[i] == -1)
      get_cc_dfs(g, i, ids, cnt++);
  vector<int> new_id_pools(cnt, 0);
  vector<int> new_ids(n);
  for(int i=0; i<n; ++i)
    new_ids[i] = new_id_pools[ids[i]]++;
  ret.resize(cnt);
  for(int i=0; i<cnt; ++i)
    ret[i] = graph(new_id_pools[i]);
  for(int i=0; i<n; ++i)
    for(int j=0; j<g[i].size(); ++j)
      ret[ids[i]][new_ids[i]].push_back(edge(new_ids[i], new_ids[g[i][j].dst], g[i][j].len, g[i][j].id));
  return ret;
}

int get_cycle_dfs(const graph& g, int v, int prev, vector<bool>& vis, vector<int>& cycle)
{
  if(vis[v]) return v;
  vis[v] = true;
  int ret = -1;
  for(int i=0; i<g[v].size(); ++i) {
    if(g[v][i].id != prev) {
      int k = get_cycle_dfs(g, g[v][i].dst, g[v][i].id, vis, cycle);
      if(k < -1) return -2;
      if(k >= 0) {
	cycle.push_back(v);
	ret = k;
	if(ret == v) return -2;
      }
    }
  }
  return ret == v ? -2 : ret;
}

vector<int> get_cycle(const graph& g)
{
  const int n = g.size();
  vector<bool> vis(n, false);
  vector<int> ret;
  get_cycle_dfs(g, 0, -1, vis, ret);
  return ret;
}

long long get_cyclepath_len(const graph& g, const vector<int>& cycle, vector<long long>& cpath_len)
{
  const int m = cycle.size();
  cpath_len.resize(m, 0);
  long long cpath_sum = 0;
  for(int i=0; i<m; ++i) {
    int next = cycle[(i+1)%m];
    for(int j=0; j<g[cycle[i]].size(); ++j) {
      if(g[cycle[i]][j].dst == next) {
	cpath_len[(i+1)%m] = g[cycle[i]][j].len;
	cpath_sum += g[cycle[i]][j].len;
      }
    }
  }
  cpath_len[0] = 0;
  for(int i=1; i<m; ++i)
    cpath_len[i] += cpath_len[i-1];
  if(cycle.size() == 2) cpath_sum >>= 1;
  return cpath_sum;
}

long long calc_max_height_dfs(const graph& g, int v, int prev)
{
  long long ret = 0;
  for(int i=0; i<g[v].size(); ++i)
    if(g[v][i].dst != prev)
      ret = max(ret, calc_max_height_dfs(g, g[v][i].dst, v) + g[v][i].len);
  return ret;
}

vector<long long> calc_max_height(const graph& g, const vector<int>& cycle)
{
  const int m = cycle.size();
  vector<long long> ret(m, 0);
  for(int i=0; i<m; ++i) {
    int prev = cycle[(i+m-1)%m], next = cycle[(i+1)%m];
    for(int j=0; j<g[cycle[i]].size(); ++j)
      if(g[cycle[i]][j].dst != prev && g[cycle[i]][j].dst != next)
	ret[i] = max(ret[i], calc_max_height_dfs(g, g[cycle[i]][j].dst, cycle[i]) + g[cycle[i]][j].len);
  }
  return ret;
}

pair<long long, int> calc_diameter_dfs(const graph& g, int v, int prev, int no1, int no2)
{
  pair<long long, int> ret(0, v);
  for(int i=0; i<g[v].size(); ++i) {
    edge e = g[v][i];
    if(e.dst != prev && e.dst != no1 && e.dst != no2) {
      pair<long long, int> tmp = calc_diameter_dfs(g, e.dst, v, no1, no2);
      tmp.first += e.len;
      if(ret.first < tmp.first) ret = tmp;
    }
  }
  return ret;
}

vector<long long> calc_diameters(const graph& g, const vector<int>& cycle)
{
  const int m = cycle.size();
  vector<long long> ret;
  for(int i=0; i<m; ++i) {
    int prev = cycle[(i+m-1)%m], next = cycle[(i+1)%m];
    pair<long long, int> a, b;
    a = calc_diameter_dfs(g, cycle[i], -1, prev, next);
    b = calc_diameter_dfs(g, a.second, -1, prev, next);
    ret.push_back(b.first);
  }
  return ret;
}

long long solve(const graph& g)
{
  if(g.size() == 1) return 0;
  vector<int> cycle = get_cycle(g);
  const int m = cycle.size();
  
  vector<long long> cpath_len;
  long long cpath_sum = get_cyclepath_len(g, cycle, cpath_len);
  vector<long long> max_height = calc_max_height(g, cycle);
  vector<long long> diameters = calc_diameters(g, cycle);

  long long ret = *max_element(diameters.begin(), diameters.end());
  long long partial_max = max_height.back() + cpath_len.back();
  for(int i=m-2; i>=0; --i) {
    ret = max(ret, max_height[i] - cpath_len[i] + partial_max);
    partial_max = max(partial_max, max_height[i] + cpath_len[i]);
  }
  partial_max = max_height.back() - cpath_len.back();
  for(int i=m-2; i>=0; --i) {
    ret = max(ret, cpath_sum + max_height[i] + cpath_len[i] + partial_max);
    partial_max = max(partial_max, max_height[i] - cpath_len[i]);
  }
  return ret;
}

int main()
{
  int N;
  graph G;
  scanf("%d", &N);
  G = graph(N);
  for(int i=0; i<N; ++i) {
    int d, l;
    scanf("%d%d", &d, &l);
    d--;
    G[i].push_back(edge(i, d, l, i));
    G[d].push_back(edge(d, i, l, i));
  }
  vector<graph> cc = get_connected_components(G);
  long long sol = 0;
  for(int i=0; i<cc.size(); ++i)
    sol += solve(cc[i]);
  printf("%lld\n", sol);
  return 0;
}

[][]IOI 2008 Egypt過去問 TYPE PRINTER

問題概要

スタックが1個あって、次の3つの操作が許されている。

  • 文字を1つpush
  • 文字を1つpop
  • スタックの底から頂点までをなぞって文字列を印字する

さて、N個の文字列が与えられるので、上の3つの操作をできるだけ少ない回数だけ使ってこれらの文字列を全て印字したい(順番は問わないし、最後の文字列を印字した後にスタックに文字が残ってても構わない)。最適な操作列を求めよ。

  • 1 <= N <= 25000
  • 1 <= 各文字列の長さ <= 20

解法

Trieを作って辿る。一番深い部分木を最後に辿れば操作回数が最小になる。


ソース

DFSがなかなか汚い。

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct trie {
  struct node {
    int cnt;
    bool leaf;
    char chr;
    node* next[26];
    node() {
      leaf = false;
      chr = '\0';
      cnt = 0;
      for(int i=0; i<26; ++i)
        next[i] = NULL;
    }
  };
  int printed, N;
  node* root;
  trie(int words) : root(new node()), N(words), printed(0) { }
  void insert(char* s) {
    node* p = root;
    while(*s) {
      if(p->next[*s-'a'] == NULL)
        p->next[*s-'a'] = new node();
      p = p->next[*s-'a'];
      p->chr = *s;
      s++;
    }
    p->leaf = true;
  }
  void dfs1(node* p) {
    p->cnt = 1;
    for(int i=0; i<26; ++i) {
      if(p->next[i] != NULL) {
        dfs1(p->next[i]);
        p->cnt = max(p->cnt, p->next[i]->cnt+1);
      }
    }
  }
  void dfs2(node* p, vector<char>& x) {
    if(p->chr != '\0')
      x.push_back(p->chr);
    if(p->leaf) {
      x.push_back('P');
      printed++;
    }
    for(int i=0; i<26; ++i)
      if(p->next[i] != NULL && p->cnt-1 != p->next[i]->cnt)
        dfs2(p->next[i], x);
    for(int i=0; i<26; ++i)
      if(p->next[i] != NULL && p->cnt-1 == p->next[i]->cnt)
        dfs2(p->next[i], x);
    if(p->chr != '\0' && printed < N)
      x.push_back('-');
  }
  void dfs1() {
    dfs1(root);
  }
  void dfs2(vector<char>& x) {
    dfs2(root, x);
  }
};

int main()
{
  int N;
  scanf("%d", &N);
  trie T(N);
  for(int i=0; i<N; ++i) {
    char str[32];
    scanf("%s", str);
    T.insert(str);
  }
  vector<char> res;
  T.dfs1();
  T.dfs2(res);
  printf("%d\n", res.size());
  for(int i=0; i<res.size(); ++i)
    printf("%c\n", res[i]);
  return 0;
}

2010-06-17

[][]IOI 2009 Bulgaria過去問 Regions

解法

まず木の節点の番号をpreorderで付け直す。すると、ある節点の子の節点の番号は連続する整数になるので、全ての節点についてその子の節点番号の区間を計算しておけば「節点bは節点aの子か?」という問にO(1)で答えることができて便利。これは木を辿るだけなのでO(N)。

次に、queryにおいてr1を固定したときにその答を効率良く計算することを考える。すなわち全ての地域 r について、 (r1, r) という形式のqueryに対する答を先に全て(効率良く)計算しておく。これは cnt1[v] に節点vから根までの最短経路に、地域 r1 から来る従業員が何人いるかを計算すれば求めることができる。cnt1[v]を全ての節点について計算するのはDFSなりを使ってO(N)。

さらに、queryにおいてr2を固定したときにその答を効率良く計算することも考える。これも先と同様に、cnt2[v] に節点vから根までの最短経路に、地域 r2 から来る従業員が何人いるかを計算して求められる。同じくDFSなどを使ってO(N)。

最後に任意のqueryを効率良く計算することを考える。ある節点vから根までの最短経路に地域 r1 からくる従業員が何人いるかを考えると、その人数によって[1, N] の区間がO(|r1|)個に分割されることがわかる(|r1| は地域 r1 から来る従業員の総数)。

f:id:JAPLJ:20100617231626p:image

たとえば図のような組織図の場合(赤は節点番号、青が出身地域)を考える。いま、地域Cについて考えると[1, N] の区間は

[1, 1], [2, 3], [4, 6], [7, 7], [8, 8], [9, 9], [10, 11], [12, 13], [14, 14], [15, 15]

と分割されることがわかる。これらの区間に属する節点から根までの最短経路に居る地域Cからの従業員の数はそれぞれ

0, 1, 2, 3, 0, 1, 1, 2, 3, 1

となる。この分割は最初にpreorderで木を辿るときに計算することができるので、全ての地域についてこの分割をO(N)で計算することができる。(上の例で連続する区間において従業員の数が同じな部分があるが、それはpreorderで木をたどりながら計算するとそういう風に分割されてしまうということである)

さて、このような分割がわかれば、r2に属するすべての節点について、r1の分割のどの区間に属するかを調べればquery (r1, r2) に対する答を計算することができる。これを高速に行うにはちょうどSweep line のような感じでr1の分割とr2の節点をなぞっていってやるとよい。計算量はO(|r1| + |r2|) 。

上で述べた3つの技法を使って100点を得ることができる。まず、最初の2つの技法だけでは100点をとるには時間もメモリも足りない。また最後の技法だけでも100点をとるには時間が足りない。

そこで、一部の地域については最初の2つの技法を使って予め答を計算しておき、残りの地域については最後の技法を使ってそのつど計算させるようにすることを考える。ここで、sqrt(N)人以上の従業員をもつ地域は高々sqrt(N)個であることを使って、人数がsqrt(N)人以上の地域については予め答を計算し、そうでない地域についてはそのつど計算させることにする。

そうすると、最初の2つの技法は高々sqrt(N)回だけ使われるので計算量は O(N*sqrt(N)) であり、最後の技法は地域の大きさが sqrt(N) より小さい地域に対してだけ使われるので計算量は O(Q*sqrt(N)) である。よって合計すると時間計算量は O(N*sqrt(N) + Q*sqrt(N)) で、空間計算量は O(R*sqrt(N) + N) であり、100点を得ることができる。

ちなみに、最後の技法での計算を二分探索で行うと、O(|r1| lg |r2|) および O(|r2| lg |r1|) 時間で1つのqueryに答えることが可能になる。この2つと O(|r1| + |r2|) のアルゴリズムを併用し、かつ従業員が多い地域に関するqueryについてはメモ化するなどすると、空間計算量をぐんと抑えて100点がとれると思う(実装はしていない)。


ソース

/*
 * task: IOI2009 Regions
 * lang: C++
 * name: JAPLJ
 */
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

int N, Q, R;
vector<int> mregions;
int mregions_ans1[500][25000], mregions_ans2[25000][500]; // < 96MB

struct node {
  int region;
  int new_idx;
  vector<int> children;
} input[200050]; // < 5MB

bool operator < (const node& a, const node& b)
{
  return a.new_idx < b.new_idx;
}

struct region_info {
  int num, id, mreg_id;
  vector<int> indices;
  vector<pair<int, int> > intervals;
  region_info() : num(0), mreg_id(-1), indices(), intervals() { }
} regions[25050]; // < 2MB

// O(N)
void dfs(int p, int& num)
{
  int reg = input[p].region;
  input[p].new_idx = num++;
  regions[reg].indices.push_back(input[p].new_idx);
  regions[reg].num++;
  regions[reg].intervals.push_back(make_pair(num, regions[reg].num));
  for(int i=0; i<input[p].children.size(); ++i)
    dfs(input[p].children[i], num);
  regions[reg].num--;
  regions[reg].intervals.push_back(make_pair(num, regions[reg].num));
}

// O(N)
void precalc_fixr1_dfs(const region_info& r, int v, vector<int>& cnt, int pnum)
{
  cnt[v] = pnum;
  if(input[v].region == r.id) pnum++;
  for(int i=0; i<input[v].children.size(); ++i)
    precalc_fixr1_dfs(r, input[v].children[i], cnt, pnum);
}

// O(N)
void precalc_fixr1(const region_info& r)
{
  vector<int> cnt(N);
  if(r.intervals.size() == 0) return;
  precalc_fixr1_dfs(r, 0, cnt, 0);
  for(int i=0; i<N; ++i)
    mregions_ans1[r.mreg_id][input[i].region] += cnt[i];
}

// O(N)
void precalc_fixr2_dfs(const region_info& r, int v, vector<int>& cnt)
{
  int num = 0;
  for(int i=0; i<input[v].children.size(); ++i) {
    precalc_fixr2_dfs(r, input[v].children[i], cnt);
    num += cnt[input[v].children[i]];
  }
  if(input[v].region == r.id) num++;
  cnt[v] = num;
}

// O(N)
void precalc_fixr2(const region_info& r)
{
  vector<int> cnt(N);
  if(r.intervals.size() == 0) return;
  precalc_fixr2_dfs(r, 0, cnt);
  for(int i=0; i<N; ++i)
    mregions_ans2[input[i].region][r.mreg_id] += cnt[i];
}

// O(r1.indices.size() + r2.indices.size())
int solve(const region_info& r1, const region_info& r2)
{
  int ret = 0, pos = 0;
  if(r1.intervals.size() == 0) return 0;
  while(pos < r2.indices.size() && r2.indices[pos] < r1.intervals[0].first)
    pos++;
  for(int i=0; i+1<r1.intervals.size() && pos<r2.indices.size(); ++i) {
    int prev = pos;
    while(pos < r2.indices.size() && r2.indices[pos] < r1.intervals[i+1].first)
      pos++;
    ret += r1.intervals[i].second * (pos - prev);
  }
  return ret;
}

int main()
{
  scanf("%d%d%d", &N, &R, &Q);
  scanf("%d", &input[0].region);
  input[0].region--;
  for(int i=1; i<N; ++i) {
    int super, region;
    scanf("%d%d", &super, &region);
    input[i].region = region-1;
    input[super-1].children.push_back(i);
  }
  int temp = 0;
  dfs(0, temp);
  for(int i=0; i<N; ++i)
    for(int j=0; j<input[i].children.size(); ++j)
      input[i].children[j] = input[input[i].children[j]].new_idx;
  for(int i=0; i<R; ++i) {
    regions[i].id = i;
    if(regions[i].indices.size() > 447) { // 447 = floor(sqrt(200000))
      mregions.push_back(i);
      regions[i].mreg_id = mregions.size()-1;
    }
  }
  sort(input, input+N);
  for(int i=0; i<mregions.size(); ++i) {
    precalc_fixr1(regions[mregions[i]]);
    precalc_fixr2(regions[mregions[i]]);
  }
  for(int i=0; i<Q; ++i) {
    int r1, r2;
    scanf("%d%d", &r1, &r2);
    r1--; r2--;
    if(regions[r1].mreg_id != -1) {
      printf("%d\n", mregions_ans1[regions[r1].mreg_id][r2]);
    } else if(regions[r2].mreg_id != -1) {
      printf("%d\n", mregions_ans2[r1][regions[r2].mreg_id]);
    } else {
      printf("%d\n", solve(regions[r1], regions[r2]));
    }
    fflush(stdout);
  }
  return 0;
}