Algoogle

Algorithm for Programming Contest

PA 2011 Plotter

Category: PA Tag: math

Plotter

問題概要


というように, 次の列は前の列の文字の間にLとRを交互に挿入したもののn個目の列を考える.

原点から初めて(1,1)に線分を伸ばしたものを考える.
そこからさっきの列を左からみていき, Lなら左に進め, Rなら右に進める.
このときm個の座標について, その点を通る回数と通る時刻を列挙せよ

解法


列は以下の様な定義に書き換えることができる.

r()は文字列の順序を反転させ, さらにLとRを入れ替えたもの.
また, が終わった時点での位置は

nは2000ぐらいだが, クエリで来る座標が程度なので終端点が大幅にはみ出たら適当に打ち切ればいい.

列の新しい定義から, 折れ線の最初と最後の2つに分けて再帰的にみれば線分上にある場合の端点からの距離がわかる.

しかしこれではで死ぬので枝刈りを入れる.
得られる折れ線を囲む四角形を考える. その外なら打ち切る.
原点からの4辺までの距離(原点は四角形の内部であることに注意する)をr, t, l, bとする.

この枝刈りは根本的で, まで削ることができる.

コード


(Plotter.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 2048;
int n, m, ex[M], ey[M], r[M], t[M], l[M], b[M];

void prepare()
{
        ex[0] = ey[0] = r[0] = t[0] = 1;
        for (int i = 1; i <= n; i++) {
                ex[i] = ex[i-1]-ey[i-1];
                ey[i] = ex[i-1]+ey[i-1];
                r[i] = max(r[i-1], t[i-1]+ex[i]);
                t[i] = max(t[i-1], l[i-1]+ey[i]);
                l[i] = max(l[i-1], b[i-1]-ex[i]);
                b[i] = max(b[i-1], r[i-1]-ey[i]);
                if(abs(ex[i]) > (1LL<<40) and abs(ey[i]) > (1LL<<40)) {
                        n = i;
                        break;
                }
        }
}

void rec(int x, int y, int n, vector<int> &s)
{
        if(-l[n] > x or x > r[n] or -b[n] > y or y > t[n]) return;
        if(n == 0) {
                if(x == y) s.assign(1,(x+y)/2);
                return;
        }
        rec(x,y,n-1,s);
        vector<int> t;
        rec(ey[n]-y,x-ex[n],n-1,t);
        for (vector<int>::iterator it = t.begin(); it != t.end(); it++)
                s.push_back((1LL<<n)-*it);
}

void solve()
{
        prepare();
        while(m--) {
                int tx, ty;
                scanf("%lld%lld", &tx, &ty);
                vector<int> ans;
                rec(tx,ty,n,ans);
                sort(ans.begin(),ans.end());
                ans.erase(unique(ans.begin(),ans.end()), ans.end());
                printf("%lld", (int)ans.size());
                for (vector<int>::iterator it = ans.begin(); it != ans.end(); it++)
                        printf(" %lld", *it);
                puts("");
        }
}

void input()
{
        scanf("%lld%lld", &n, &m);
}

signed main()
{
        input();
        solve();
        return 0;
}

Comments