DouKaku?beta

[topic] 情報オリンピック2007年度国内本選問題5

中高生向けの情報オリンピック国内本選2007年度問題5です。

問題文（下記PDFの11ページ目）
http://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf
コンテスト概要
http://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/index.html
サンプルデータ（出題時に公開）
http://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/joi2008.zip
採点データ（出題時に非公開）
http://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/data.zip

「問題ごとに、プログラムの実行時間（や使用メモリ量）に制限が設定されています。」にご注意ください。本問では、制限時間1秒、メモリ制限64MBとなっています。

出題時はサンプルデータのみが公開され、採点は、採点データによる、自動採点にて行われます。

実際のコンテストでは、予選通過者48名が対象となっていて、100点満点中38点以上とった、16名が本選通過です。

post comment

Posted feedbacks - Flatten

Nested Hidden 
ブログのほうでリクエストがありましたので書き込ませていただきます。
公式ジャッジデータで時間内に正答することは一応確認しています。
少しでも参考になれば幸いです。

see: JOI2007-2008 Honsen 

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

#define ALLOF(c) (c).begin(),(c).end()
#define DEBUG(c) cerr<<"> "<<#c<<" = "<<c<<endl;

using namespace std;

typedef pair<int,int> pt;

void coordinate_compression(vector<pt> &p1,vector<pt> &p2)
{
    vector<int> tx,ty;
    for(int i=0;i<p1.size();i++)
    {
        tx.push_back(p1[i].first);
        ty.push_back(p1[i].second);
        tx.push_back(p2[i].first);
        ty.push_back(p2[i].second);
    }
    
    sort(ALLOF(tx));
    sort(ALLOF(ty));
    tx.erase(unique(ALLOF(tx)),tx.end());
    ty.erase(unique(ALLOF(ty)),ty.end());
    
    for(int i=0;i<p1.size();i++)
    {
        p1[i].first=lower_bound(ALLOF(tx),p1[i].first)-tx.begin();
        p1[i].second=lower_bound(ALLOF(ty),p1[i].second)-ty.begin();
        p2[i].first=lower_bound(ALLOF(tx),p2[i].first)-tx.begin();
        p2[i].second=lower_bound(ALLOF(ty),p2[i].second)-ty.begin();
    }
    
    return;
}

void part_fill(vector<pt> &p1,vector<pt> &p2,vector<vector<int> > &m)
{
    
    vector<pair<pt,int> > p;
    
    for(int i=0;i<p1.size();i++)
    {
        for(int j=p1[i].first;j<p2[i].first;j++)
        {
            p.push_back(make_pair(make_pair(j,p1[i].second),0));
            p.push_back(make_pair(make_pair(j,p2[i].second),1));
        }
    }
    
    sort(ALLOF(p));
    
    pt s;
    int cnt=0;
    for(int i=0;i<p.size();i++)
    {
        pt t=p[i].first;
        int flg=p[i].second;
        if(flg==0)
        {
            if(!cnt++)
                s=t;
        }
        
        if(flg==1)
        {
            if(!--cnt)
            {
                for(int j=s.second;j<t.second;j++)
                    m[j][s.first]=1;
            }
        }
    }
    
    return;
}

void consecutive_part_fill(int x,int y,vector<vector<int> > &m)
{
    int h=m.size();
    int w=m[0].size();
    
    queue<pt> q;
    q.push(make_pair(x,y));
    
    while(!q.empty())
    {
        int cx=q.front().first;
        int cy=q.front().second;
        q.pop();
        
        static int dx[]={1,-1,0,0};
        static int dy[]={0,0,1,-1};
        
        for(int i=0;i<4;i++)
        {
            int tx=cx+dx[i];
            int ty=cy+dy[i];
            
            if(tx<0 || tx>=w || ty<0 || ty>=h)
                continue;
            
            if(!m[ty][tx])
            {
                m[ty][tx]=1;
                q.push(make_pair(tx,ty));
            }
        }
    }
    
    return;
}

int main()
{
    int w,h; cin>>w>>h;
    int n; cin>>n;
    
    vector<pt> p1(n),p2(n);
    for(int i=0;i<n;i++)
        cin>>p1[i].first>>p1[i].second>>p2[i].first>>p2[i].second;
    
    p1.push_back(make_pair(0,0));
    p2.push_back(make_pair(w,h));
    
    coordinate_compression(p1,p2);
    
    w=p2.back().first;
    h=p2.back().second;
    p1.pop_back();
    p2.pop_back();
    
    vector<vector<int> > m(h,vector<int>(w,0));
    
    part_fill(p1,p2,m);
    
    int res=0;
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(!m[i][j])
            {
                res++;
                m[i][j]=1;
                consecutive_part_fill(j,i,m);
            }
        }
    }
    
    cout<<res<<endl;
    
    return 0;
}

時間内に終わらないデータがありますが（確か5-11）せっかくなので投稿。結局 map を少しずつ大きくしていくのは無駄で、hyon さんのようにがばっとマスキングテープの座標を vector に入れて、がばっと map を作成すべき。（あとで試してみるつもり）

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <cassert>

#define REP(i, b, e) for (size_t i = b; i < e; ++i)

size_t insert_x(std::vector<long>& xs, std::vector<std::vector<int> >& map, long x)
{
    std::vector<long>::iterator it = std::lower_bound(xs.begin(), xs.end(), x);

    const size_t i = it - xs.begin();

    if (*it != x)
    {
        xs.insert(it, x);

        assert(i >= 1);

        map.insert(map.begin() + i, map[i - 1]);
    }

    return i;
}

size_t insert_y(std::vector<long>& ys, std::vector<std::vector<int> >& map, long y)
{
    std::vector<long>::iterator it = std::lower_bound(ys.begin(), ys.end(), y);

    const size_t i = it - ys.begin();

    if (*it != y)
    {
        ys.insert(it, y);

        assert(i >= 1);

        REP(j, 0, map.size())
        {
            map[j].insert(map[j].begin() + i, map[j][i - 1]);
        }
    }

    return i;
}

int main()
{
    long w, h;

    std::cin >> w >> h;

    assert(0 <= w && w <= 1000000);
    assert(0 <= h && h <= 1000000);

    size_t n;

    std::cin >> n;

    assert(1 <= n && n <= 1000);

    std::vector<long> xs(2); xs[0] = 0; xs[1] = w;

    std::vector<long> ys(2); ys[0] = 0; ys[1] = h;

    std::vector<std::vector<int> > map(1, std::vector<int>(1, true));

    for (; n; --n)
    {
        long left, bottom, right, top; // masking tape

        std::cin >> left >> bottom >> right >> top;

        assert(left < right);

        assert(bottom < top);

        const size_t lower_xi = insert_x(xs, map, left);

        const size_t upper_xi = insert_x(xs, map, right);

        const size_t lower_yi = insert_y(ys, map, bottom);

        const size_t upper_yi = insert_y(ys, map, top);

        REP(xi, lower_xi, upper_xi) REP(yi, lower_yi, upper_yi)
        {
            map[xi][yi] = false;
        }
    }

    const size_t xn = xs.size() - 1;

    const size_t yn = ys.size() - 1;

    size_t count = 0;

    REP(xi, 0, xn) REP(yi, 0, yn) if (map[xi][yi])
    {
        ++count;

        std::queue<std::pair<size_t, size_t> > q;

#define PUSH(XI, YI) if (map[XI][YI]) { map[XI][YI] = false; q.push(std::make_pair(XI, YI)); }

        PUSH(xi, yi);

        while (! q.empty())
        {
            const size_t xj = q.front().first;

            const size_t yj = q.front().second;

            q.pop();

            if (xj >= 1) // left
            {
                PUSH(xj - 1, yj);
            }

            if (yj >= 1) // top
            {
                PUSH(xj, yj - 1);
            }

            if (xj + 1 < xn) // right
            {
                PUSH(xj + 1, yj);
            }

            if (yj + 1 < yn) // bottom
            {
                PUSH(xj, yj + 1);
            }
        }

#undef PUSH

    }

    std::cout << count << std::endl;
}

map を一気に作るようにしてみましたが、それだけじゃ不足みたいですね・・・速くはなったけど依然時間何に終わらず。飽きたのでとりあえずここまで。

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <cassert>

#define REP(i, b, e) for (size_t i = b; i < e; ++i)

struct rect
{
    long left, bottom, right, top;
};

template <typename T>
void sort_and_unique(std::vector<T>& v)
{
    std::sort(v.begin(), v.end());

    v.erase(std::unique(v.begin(), v.end()), v.end());
}

template <typename T>
size_t find(const std::vector<T>& v, const T& value)
{
    std::vector<T>::const_iterator it = std::lower_bound(v.begin(), v.end(), value);

    assert(it != v.end());

    return it - v.begin();
}

int main()
{
    long w, h;

    std::cin >> w >> h;

    assert(0 <= w && w <= 1000000);
    assert(0 <= h && h <= 1000000);

    size_t n;

    std::cin >> n;

    assert(1 <= n && n <= 1000);

    std::vector<rect> tapes;

    for (; n; --n)
    {
        rect r;

        std::cin >> r.left >> r.bottom >> r.right >> r.top;

        assert(0 <= r.left && r.left < r.right && r.right <= w);

        assert(0 <= r.bottom && r.bottom < r.top && r.top <= h);

        tapes.push_back(r);
    }

    std::vector<long> xs(2); xs[0] = 0; xs[1] = w;
    std::vector<long> ys(2); ys[0] = 0; ys[1] = h;

    for (std::vector<rect>::const_iterator it = tapes.begin(); it != tapes.end(); ++it)
    {
        xs.push_back(it->left);
        xs.push_back(it->right);
        ys.push_back(it->bottom);
        ys.push_back(it->top);
    }

    sort_and_unique(xs);
    sort_and_unique(ys);

    const size_t xn = xs.size() - 1;
    const size_t yn = ys.size() - 1;

    std::vector<std::vector<int> > map(xn, std::vector<int>(yn, true));

    for (std::vector<rect>::const_iterator it = tapes.begin(); it != tapes.end(); ++it)
    {
        const size_t lower_xi = find(xs, it->left);
        const size_t upper_xi = find(xs, it->right);
        const size_t lower_yi = find(ys, it->bottom);
        const size_t upper_yi = find(ys, it->top);

        REP(xi, lower_xi, upper_xi) REP(yi, lower_yi, upper_yi)
        {
            map[xi][yi] = false;
        }
    }

    size_t count = 0;

    REP(xi, 0, xn) REP(yi, 0, yn) if (map[xi][yi])
    {
        ++count;

        std::queue<std::pair<size_t, size_t> > q;

#define PUSH(XI, YI) if (map[XI][YI]) { map[XI][YI] = false; q.push(std::make_pair(XI, YI)); }

        PUSH(xi, yi);

        while (! q.empty())
        {
            const size_t xj = q.front().first;

            const size_t yj = q.front().second;

            q.pop();

            if (xj >= 1) // left
            {
                PUSH(xj - 1, yj);
            }

            if (yj >= 1) // top
            {
                PUSH(xj, yj - 1);
            }

            if (xj + 1 < xn) // right
            {
                PUSH(xj + 1, yj);
            }

            if (yj + 1 < yn) // bottom
            {
                PUSH(xj, yj + 1);
            }
        }

#undef PUSH

    }

    std::cout << count << std::endl;
}

memsetを使うようにしたところ，大幅に高速化しました。

 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
--- 5.cpp    Wed Jun 25 16:56:20 2008
+++ 5.cpp    Sat Jun 28 20:33:02 2008
@@ -5,6 +5,7 @@
 #include <queue>
 #include <utility>
 #include <cassert>
+#include <cstring> // memset()
 
 #define REP(i, b, e) for (size_t i = b; i < e; ++i)
 
@@ -24,7 +25,7 @@
 template <typename T>
 size_t find(const std::vector<T>& v, const T& value)
 {
-    std::vector<T>::const_iterator it = std::lower_bound(v.begin(), v.end(), value);
+    typename std::vector<T>::const_iterator it = std::lower_bound(v.begin(), v.end(), value);
 
     assert(it != v.end());
 
@@ -78,7 +79,7 @@
     const size_t xn = xs.size() - 1;
     const size_t yn = ys.size() - 1;
 
-    std::vector<std::vector<int> > map(xn, std::vector<int>(yn, true));
+    std::vector<std::vector<unsigned char> > map(xn, std::vector<unsigned char>(yn, 1));
 
     for (std::vector<rect>::const_iterator it = tapes.begin(); it != tapes.end(); ++it)
     {
@@ -87,9 +88,9 @@
         const size_t lower_yi = find(ys, it->bottom);
         const size_t upper_yi = find(ys, it->top);
 
-        REP(xi, lower_xi, upper_xi) REP(yi, lower_yi, upper_yi)
+        REP(xi, lower_xi, upper_xi)
         {
-            map[xi][yi] = false;
+            std::memset(&map[xi][lower_yi], 0, (upper_yi - lower_yi) * sizeof(unsigned char));
         }
     }

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]