DouKaku?beta

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

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

問題文（下記PDFの6ページ目）
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
#include<iostream>
#include<vector>
#include<algorithm>

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

using namespace std;

int main()
{
    int n,m; cin>>n>>m;
    
    vector<int> seq(n);
    for(int i=0;i<n;i++)
        cin>>seq[i];
    
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            seq.push_back(seq[i]+seq[j]);
    
    sort(ALLOF(seq));
    seq.erase(unique(ALLOF(seq)),seq.end());
    seq.erase(upper_bound(ALLOF(seq),m),seq.end());
    
    int res=seq.back();
    int j=seq.size()-1;
    for(int i=0;i<seq.size();i++)
    {
        for(;j>=i && seq[i]+seq[j]>res;j--)
        {
            if(seq[i]+seq[j]<=m)
            {
                res=seq[i]+seq[j];
                break;
            }
        }
    }
    
    cout<<res<<endl;
    
    return 0;
}


しらみつぶしだと O(N^4) です。20％の得点がもらえます。

3本までをしらみつぶしでやり、最後2分探索すると
O(N^3 log N) で50％の得点がもらえます。

4本＝2本＋2本であることに着目すると、2本までをしらみつぶしでやり、
最後2分探索すると O(N^2 log N) になり、満点となります。

【擬似コード】

データを読み込む。データに0を追加
N^2 の組み合わせを作る
それをソートする
for x <- N^2 の組み合わせで M 以下
    2分探索で、M-x 以下で最大の物を探し、xとの和をとる。
    その最大値が答え

 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class P3 {
    public static void main(String[] args) throws Exception {
        // データの読み込み。データに０を追加
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] ary = in.readLine().split(" ");
        int N = Integer.parseInt(ary[0]);
        int M = Integer.parseInt(ary[1]);
        N++;
        int[] data = new int[N];
        for (int i = 1; i < N; i++) {
            data[i] = Integer.parseInt(in.readLine());
        }

        // N^2 の組み合わせを作る
        int[] comb = new int[N * N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                comb[i * N + j] = data[i] + data[j];
            }
        }
        // それをソートする
        Arrays.sort(comb);

        // for x <- N^2 の組み合わせで M 以下
        int max = 0;
        for (int i = 0; i < comb.length; i++) {
            int x = comb[i];
            if (x > M)
                break;
            // 2分探索で、M-x以下で最大の物を探し、xとの和をとる。
            int bs = Arrays.binarySearch(comb, M - x);
            if (bs < 0) {
                bs = -(bs + 1);
            } else if (bs != comb.length) {
                max = M;
                break;
            }
            if (bs > 0) {
                max = Math.max(max, x + comb[bs - 1]);
            }
        }
        System.out.println(max);
    }
}


 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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

typedef unsigned long ulong;

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());
}

int main()
{
    size_t N;

    ulong M;

    assert(std::cin);

    std::cin >> N >> M;

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

    assert(1 <= M && M <= 200000000);

    // allows 1 throw

    std::vector<ulong> s1(1, 0); // 0 point == no throw

    s1.reserve(N + 1);

    for (size_t i = 0; i < N; ++i)
    {
        ulong p;

        assert(std::cin);

        std::cin >> p;

        assert(1 <= p && p <= 100000000);

        if (p <= M)
        {
            s1.push_back(p);
        }
    }

    sort_and_unique(s1);

    // allows 2 throw

    std::vector<ulong> s2;

    s2.reserve(s1.size() * s1.size());

    for (size_t i = 0; i < s1.size(); ++i)
    {
        for (size_t j = 0; j < s1.size() && s1[i] + s1[j] <= M; ++j)
        {
            s2.push_back(s1[i] + s1[j]);
        }
    }

    sort_and_unique(s2);

    // allows 4 throw

    ulong max_point = 0;

    std::vector<ulong>::reverse_iterator rit = s2.rbegin();

    for (std::vector<ulong>::iterator it = s2.begin(); it != s2.end(); ++it)
    {
        while (rit != s2.rend() && *it + *rit > M)
        {
            ++rit;
        }

        if (rit == s2.rend())
        {
            break;
        }

        max_point = std::max(max_point, *it + *rit);
    }

    std::cout << max_point << std::endl;
}

Index

Feed

Other

Link

Pathtraq

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