HashCode 2020

Share

Hash Code 是由Google举办，并且每一年举办一次的大型编程比赛。今年的比赛官网

关于最终比赛结果，在一共10724份提交代码的小组中，我们最终积分是两千四百多万分，具体排名为2100名。感谢小组内所有大佬的付出，让我们4个小时的努力有所回报。

今年的比赛题目和数据集见此。该仓库包含今年的练习题目与正式题目。此篇文章主要陈述正式比赛题目中的数据集b和d的解法。

至于为什么只写这两个数据集的解法，因为是我写的。但是关于d的算法在数据集d上的实现并不好，然而在f上的实现超出预期。

题目

先简单介绍一下题目的大概意思。当然，如果你想真正了解题目，还是建议去看上文仓库链接中的源文件。

题目的主要目的是让我们给出一个算法，可以在规定的时间内扫描书目，保证书目的数量尽可能多时，同时保证被扫描的书目的权重和越大。该权重和就是最后比赛的成绩。

题目中主要有三个约束条件，一个是图书馆，一个是图书，一个是总时间。这些具体见后文的代码。首先先分析输入数据集的具体意义。

输入数据集总体分为两部分，第一部分为前两行，剩下的为第二部分。在第一部分中，第一行的三个数字分别代表了总的图书数量、总的图书馆数量和总的日期；第二行为每个图书的具体权重。在第二部分中，又以每两行为单位定义了一个图书馆的属性；每组的第一行的三个数字分别代表了该图书馆总的图书数量、注册需要的时间和每天能运输的图书能力，每组的第二行表示该图书馆所存放的图书序号。

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
// 图书馆数据结构
struct Library {
    // 注册时间
    unsigned long long signup_time;
    // 每天可运输的图书数量
    unsigned long long ships_per_day;
    // 存放的图书
    unordered_set<unsigned long long> lib_books;
    // 已经扫描的图书
    vector<unsigned long long> to_scan;

    // 判断是否还能继续扫描
    bool canScan() const {
        return (days - signup_time) * ships_per_day - to_scan.size() > 0;
    }

    // 计算该图书馆权重
    unsigned long long potentialScore() const {
        unsigned long long s = 0;
        for (auto b : to_scan) {
            s += books[b];
        }
        return s;
    }
};

这里需要注意的是，在图书馆注册期间，是不允许运输图书的，而且注册之后每天运输的图书不允许超过其最大承受容量。但是是允许多线程工作的，详细见下图。

题目规定最后的标准输出也具体分为两部分。第一部分单独成一行，并且只有一个数据，表示一共可以注册的图书馆总数。第二部分以每两行为一组，第一行包含两个数据，分别代表该被选中的图书馆的序号和一共运输的图书数量；第二行为被运输数量的序号。需要注意的是，结果中如果有重复的书目数据，成绩只会登记一次。详细见下图。

题目整体介绍到这里。还是那句话，如果想真正了解题目，建议去看上文仓库链接。

数据集b的解法

首先先分析一下数据集的构成。b这个数据集很有取巧性，不难发现，该数据集的每本数量的权重是一样的，并且每个图书馆的总图书数量和每天可以运输的图书数目是一样的。下图为b数据集的部分截图。详细数据集

所以破解b数据集很明显的算法就是贪心算法，对每个图书馆的注册时间进行贪心，从小排列到大，依次入栈，直到超出所给的总时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solutionB() {
    vector<pair<unsigned long long, unsigned long long>> libs_todo_index(libs.size());
    // 将所有图书馆入栈并按照注册时间排序
    for (unsigned long long i = 0; i < libs.size(); i++) {
        libs_todo_index[i].first = libs[i].signup_time;
        libs_todo_index[i].second = i;
    }
    sort(libs_todo_index.begin(), libs_todo_index.end());
    unordered_set<unsigned long long> add_books;
    // 开始扫描图书
    // 同时注意判断是否超出总时间以及是否重复
    for (unsigned long long i = 0; i < libs_todo_index.size(); i++) {
        Library& lib = libs[libs_todo_index[i].second];
        for (auto book : lib.lib_books) {
            if (!add_books.count(book) && lib.canScan()) {
                lib.to_scan.push_back(book);
                add_books.insert(book);
            }
        } 
    // 将结果入栈  
    libraries.push_back(libs_todo_index[i].second);
    }
}

因为数据集b的构成十分简单，所以使用贪心得出的应该是最优解。

数据集d的解法

数据集d的构成和b很类似，每个图书馆的注册时间和每天所承受最大运输数一样，只有每个图书馆所含图书数量不一样。详细数据集

在处理d数据集的时候，由于前期思考使用的数据结构和算法取舍上花费了比较多的时间，这里就在对d处理的基础上，向其他数据集进行了扩展。首先先对所有图书的权重进行从大到小排序，然后按照图书馆的注册时间对每个图书馆进行从小到大排序。

然后以图书的权重顺序为外层循环条件，以图书馆注册时间为内层循环条件，将图书馆所存放图书按照权重入栈。最后计算所有图书馆的得分权重，按照从大到小排序入栈最终结果。

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
void solution() {
    // 首先把所有图书按照权重排序
    vector<pair<unsigned long long, unsigned long long>> book_score_todo_index(books.size());
    for (unsigned long long i = 0; i < books.size(); i++) {
        book_score_todo_index[i].first = books[i];
        book_score_todo_index[i].second = i;
    }
    sort(book_score_todo_index.begin(), book_score_todo_index.end());
    
    // 把所有图书馆按照注册时间排序
    vector<pair<unsigned long long, unsigned long long>> libs_todo_index(libs.size());
    for (unsigned long long i = 0; i < libs.size(); i++) {
        libs_todo_index[i].first = libs[i].signup_time;
        libs_todo_index[i].second = i;
    }
    sort(libs_todo_index.begin(), libs_todo_index.end());

    // 开始计算每个图书馆的具体权重
    // 注意要去除重复出现的图书
    unordered_set<unsigned long long> libs_set;
    for (unsigned long long i = book_score_todo_index.size() - 1; i >= 0; i--) {
        for (unsigned long long j = libs_todo_index.size() - 1; j >= 0; j--) {
            Library& lib = libs[libs_todo_index[j].second];
            if (lib.canScan() && lib.lib_books.count(i)) {
                lib.to_scan.push_back(i);
                libs_set.insert(libs_todo_index[j].second);
                break;
            }
        }
    }
	
    // 按图书馆的权重和入栈到最终结果
    vector<pair<unsigned long long, unsigned long long>> score_index;
    score_index.reserve(libs_set.size());
    for (auto id : libs_set) {
        score_index.emplace_back(libs[id].potentialScore(), id);
    }
    sort(score_index.begin(), score_index.end());
    reverse(score_index.begin(), score_index.end());
    for (int i = 0; i < score_index.size(); i++) {
        libraries.push_back(score_index[i].second);
    }
}

这样的双重贪心不可避免的损失精度，所以必定不是最优解。所以数据集d最后只有四百多万的积分。但是在计算真实世界的数据集f时，却达到了五百多万的积分，超乎意料。

最后

附上我们小组的每个数据集的具体得分。

这里吐槽一下，Google在example上跟我们玩了个游戏，因为题目中给出的example并不是最优解。

使用C++进行数据处理，可能唯一的优势就是速度了，但是在选择保存和处理数据的数据结构的选择上真是仿佛吃屎，从开始的类到三维数组再到最后使用的结构体真的很折腾人，这部分花费了太多时间，主要原因还是自己接触这种数据的次数过少，没能在第一时间选择出合理的数据结构。其次，文件的读写真的没有python便捷。

如果时间再充裕些，就可以对数据集c和d算法进行再次优化，让每个的最后积分再增加一百万达到五百万级别，到时我们就有可能冲击决赛名额，啧，算是比较遗憾吧。

但是整体来说，这次比赛极大的加深了我对unordered_set和pair这两个经典的STL数据结构的理解和使用。

而且最后的总分远远超出我们所有人最开始的估计，而且最后的排名也不错，虽说肯定进不了决赛了，但是总体排名前20%还是可以写进简历的。

以及加♂深了和各位大佬的友谊。

最最后

今天早上刚醒就收到了挚友韩静轩发来的消息，他和她女朋友分别以407和397的考研成绩成功考上哈工大建筑系，可喜可贺可喜可贺。