Algoogle

Algorithm for Programming Contest

JOI 春合宿 2012 JOI Flag

Category: JOI Tag: implementation

JOI Flag

問題概要


以下の操作で塗られる旗を考える.
1辺が2^Kの正方形を4つの等しい大きさの正方形に分解する.
そのうち3つはJ, O, Iを割り当てて埋める.
残りの1つは再帰的に同じ操作を繰り返す.
1マスしか残らなかったらJOIのいずれかを割り当てる.

今N箇所がJOIのいずれかで塗られている旗がある.
上の操作をして旗をつくりたい.
既に塗られているマスを別の文字に変えるのにはコスト1かかる.
コストの最小はいくらか

解法


再帰的に分解しながらやればよい.
各エリアに何個J, O, Iがそれぞれあるかと, そのエリアをまた分割する場合の最小のコストを求めていけばその正方形に対する最小のコストが求められる.
今回はある正方形に対して
左下<右下<左上<右上
と再帰的に定義してソートしておくことで各個数をO(KlogN)程度で求めた.
実行時間に余裕があったようで毎回O(N)でカウントしても良かったらしい(空間に対してNが小さいので枝刈りで大幅に削れる).
なので以下は蛇足.

上の順番付けは2点を含む正方形のうち, 分割すると異なる正方形にそれぞれが属するような正方形を考えた.
これは2点のx座標のビット列で異なるビットの最上位の値が分割された正方形の1辺の長さになるのでMSBを求めれば良い.
y座標についても同様にやって大きい方を採用する.
そのビットより上のビットは共通しているので立てたまま, 下のビットは0にしてやれば境界が求まる.
この境界を元に上の大小関係を満たすように番号付けすれば2点の比較ができる.
この順にならんでいればあとはupper_bound-lower_boundで個数が求まる

コード


(joiflag.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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;

struct point
{
        int x, y;
        point(){}
        point(int x, int y):x(x),y(y){}
        int msb(const int &k) const {
                int x = -1, y = k;
                while(y) {
                        x = y&-y;
                        y -= x;
                }
                return x;
        }
        bool operator<(const point &p) const {
                int tx = msb(x^p.x), ty = msb(y^p.y);
                if(tx < 0 and ty < 0) return 0;
                int mx = ((x&p.x)&(-1^(tx-1)))|tx, my = ((y&p.y)&(-1^(ty-1)))|ty;
                if(tx > ty) my = ((y&p.y)&(-1^(tx-1)))|tx;
                else mx = ((x&p.x)&(-1^(ty-1)))|ty;
                return (((y>=my)<<1)|(x>=mx)) < (((p.y>=my)<<1)|(p.x>=mx));
        }
};

const string joi = "JOI";
int k, n;
vector<point> ps[3];

int rec(int lv, int lx, int ly)
{
        if(lv == 0) return 0;
        int memo[4][4], d = 1<<(lv-1);
        memset(memo,-1,sizeof(memo));
        const int x[] = {lx, lx+d}, y[] = {ly, ly+d};
        vector<int> fs = {0,1,2,3};
        int ret = -1;
        do {
                int tmp = 0;
                for (int i = 0; i < 4; i++) {
                        int &res = memo[i][fs[i]];
                        if(~res) {
                                tmp += res;
                                continue;
                        }
                        res = 0;
                        if(fs[i] == 3) res = rec(lv-1,x[i%2],y[i/2]);
                        else {
                                for (int j = (fs[i]+1)%3; j != fs[i]; j=(j+1)%3) {
                                        res += upper_bound(begin(ps[j]),end(ps[j]), point(x[i%2]+d-1,y[i/2]+d-1))
                                              -lower_bound(begin(ps[j]),end(ps[j]), point(x[i%2],y[i/2]));
                                }
                        }
                        tmp += res;
                }
                ret = ret<0? tmp: min(ret, tmp);
                if(!ret) return ret;
        } while(next_permutation(begin(fs),end(fs)));
        return ret;
}

int solve()
{
        for (int i = 0; i < 3; i++) sort(begin(ps[i]),end(ps[i]));
        return rec(k,0,0);
}

void input()
{
        cin >> k >> n;
        int x, y; char c;
        for (int i = 0; i < n; i++) {
                cin >> x >> y >> c;
                x--; y--;
                ps[joi.find(c)].push_back(point(x,y));
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments