开启梦想之门——竞赛题目解读

收藏

第一篇：题目解读

各位同学，大家好！
本届竞赛的题目——《筑梦之城》已经公布半个月了，相信大家通过阅读题目文档，参加校园宣讲，互相讨论等方式，已经对题目有了比较深刻的认识。
不过在这里，我还是要费费口舌，帮大家解读一下本次竞赛的题目，说一些在设计之时的所想。如果下面所说的，你已经正确地理解，那么祝你能更快地设计出优秀的算法；如果有什么地方与你之前的理解不尽相同，欢迎回帖参与讨论，我们的目的就是弄清题目中的每一个细节！
那么，闲话少说，解读开始！

首先，我们从地图说起。
地图，包含基本属性：宽和高。宽和高的定义，是地图上每行和每列的单元格的个数。单元格，即地图上的最小单元，同时作为地图尺寸的量度，它是一个正方形的区域。
在地图的每个单元格上，有两个重要的属性。一个是类型，一个是状态。
单元格的类型，共有五种，即：非建筑用地，未指定功能的区域，生活区，工业区以及商业区。
非建筑用地，即不能放置建筑的区域；
未指定功能的区域，可以放置建筑，但不会有额外的奖励；
生活区，工业区和商业区，均可放置建筑。放置的建筑既可以是相同类型的，也可以是不同类型的。但放置相同类型的建筑会有额外的奖励。
地图的每个单元格，还有一个状态的属性。这个属性指示一个单元格是空的，还是已经被某个选手的算法占用。

再说建筑。
与地图类似，建筑也有宽和高两个基本属性。建筑的宽和高指示的是建筑布局的总的大小，而不是布局中建筑的实际占用部分的大小。
建筑的尺寸的量度，是与地图上单元格等大的格子数。
建筑也有类型属性。与地图类似的，建筑的类型分为住宅，工厂和商场。但与地图上单元格的类型不同的是，一，每个建筑只有一个属性，其全部组成部分均为这一类型；二，建筑的类型仅限于上述的三种，没有不能放置在任何区域的建筑，也没有无类型的建筑。
建筑布局中的每个格子，有一个状态属性。这个属性可以为两种状态，它表示该格子是否是建筑的组成部分。如果一个在建筑布局中的格子不是该建筑的一部分，那么它在摆放时可以被忽略不计，即它可以被放置在任意区域。

关于建筑的摆放。
建筑在摆放之前是可以进行旋转的。建筑的旋转以90度为单位，沿顺时针方向进行。
将建筑放置在地图上，需要给定一个座标。这个座标是地图座标系下的，它指示将（旋转后的）建筑布局的左上角，放置在地图上的某一位置。
摆放建筑时，要确定以下几点：
1.建筑的各组成部分均未覆盖地图上的非建筑用地；
2.建筑的各组成部分均在地图边界范围内；
3.建筑的各组成部分均未覆盖地图上已经被其它建筑覆盖的区域。
每个建筑在一局比赛中都只能使用一次。
如果放置建筑时没有满足以上条件，或者使用了可以建筑之外的建筑，都属于错误放置。错误放置不会导致地图和可用建筑的变化。

关于分数。
成功放置建筑，可以获得与建筑面积（组成建筑的小格子的个数）相同的分数。
建筑覆盖同类型的地图区域，每覆盖一个多得1分。
一局比赛正常结束时，如果某算法放置的建筑（无论类型），覆盖了地图上某一类型（住宅区、工业区及商业区）的格子超过一半，那么该算法放置的这一类型的建筑，每建筑（而不是每个同类型覆盖的格子）获得2分的奖励。
每次错误的放置减3分。
如果一局比赛非正常结束，那么过错方（即导致这局比赛非正常结束的一方）得0分，另一方的得分，是这局比赛开始时，全部可用建筑面积之和。
算法在一局比赛中的最低得分为0分。

关于规则。
一局比赛有两个选手的算法对战。算法实例在构造时被分配A或B做为一局比赛中的ID，这个ID一经分配，在一局比赛中便不会改变。
在一局比赛中，两个算法被伺服程序按照ABBAABBAA……的顺序调用（即每回合轮先，第一局由ID为A的算法先行）。
算法在每一次被调用时，可以选择在某地图区域放置一个建筑，或者什么都不做。
算法须严格地遵守时间和空间约束。
第一次的调用，应在1s内返回，一局游戏，包含算法实例构造的时间在内，一个算法可用的总时间为30s。
算法被调用时，可用的内存为512MB；算法返回时，驻留内存的部分占用空间应在256MB以内。
超出时间和空间约束的算法，会被判负。
出现以下情况的算法也会被判负：
调用过程中有异常抛出；
使用被禁止使用的技术或手段，破坏比赛环境或公平性。禁止使用的技术或手段包括但不限于：使用I/O功能、使用反射功能等。

以上内容，部分来自题目文档本身，部分在校园宣讲时已经有过介绍，在这里做一个总结，方便大家查阅。
近期会更新一些对题目的分析，敬请期待！
如果大家有什么想法，欢迎交流讨论

Iver · Iver

第二篇：浅谈算法设计思路

大家好！
在上一篇中，我不厌其烦地又把校园宣讲时说过好次的内容敲了一遍，只是希望对那些没能参加的同学能有一点点的帮助

这一篇，就跟大家分享一下我对这个题目算法设计的一点想法。

首先，有一点要声明：以下内容只是我的一些想法，可能有不妥当之处，也难免有疏漏之处，大家在实际设计和编写算法的时候，还是要自己多想多尝试，不能简单地把以下内容代码化:Z 。
其次，欢迎大家回帖进行讨论，都说说自己的看法。这次竞赛本来就是一个难得的交流的机会，我相信学到知识，得到成长才是最重要的。
最后（正文开始之前的最后……），我个人不对下面的内容保留任何著作权

，也希望大家遵循这样的约定，拣点可以让别人拿去用的东西交流

时间篇
对于算法的时间限制，包含两条，即单步时间和总时间，具体的内容楼上有介绍，这里不再赘述。

如何保证算法的耗时不至超出规定的时间限制呢？
在题目文档的最后，示例代码中演示了一个计时框架。在那段代码中，使用了Stopwatch进行方法内的计时，考虑了单步时间和总耗时，并且给出了一下buffer的空间，防止因为方法调用、返回、以及其它不可预期的情况造成意外超时。这个框架演示的方法应该还是值得借鉴的，但是其中的一些硬编码的数值可以根据个人的需要或者实际测试数据来确定。
如果算法的一次调用要执行大量操作，那么应该将这些任务合理地划分成子任务，并保证子任务消耗的时间不至于过长。同时，在子任务衔接的时间点，适时地检查剩余时间，防止超时。

如何合理地规划利用时间呢？
一局比赛的总可用时间是固定的，每一回合的可用时间也是固定的，但不同的数据需要执行的回合数和需要处理的数据量却是不确定的！
所以，在一局比赛中的某个时刻（通常是开始时），大致地估算比赛的进程是一个有意义的尝试。通过分析数据，大致估算一局比赛要进行多少回合，这样对于合理利用时间，使每一次被调用时的用时更高效是很有帮助的。
另外，通过分析已经执行的操作和当前地图信息，实时地更新时间片使用规划，能够更好地利用剩余的时间。

如何应对大规模的数据呢？
很多同学都问到建筑列表的规模问题，我的回答是没有确定上限。
这样的设置，是对选手算法数据处理能力的一个考验。建筑的数量可能会很大，如何有效地处理大量数据，既保证不超出规定的时间，又得到较高的分数是算法优化的一个重要方向。
简单地说，保留中间结果，减少重复操作、分批处理，避免单次处理过多数据、适当取舍，退而求其次，这些都是可以考虑的方法。

空间篇
算法的空间限制，同样有两条，详见上文。

如何控制和计算算法的空间使用呢？
竞赛平台并没有提供算法内存使用情况的相关信息。所以，在内存控制这方面，选手需要靠自己的努力了

其实，通常情况下，算法使用的内存，只需要被控制在一个比较粗略的范围内，比方说200MB。这样，查看Windows任务管理器中的内存使用量变化就可以大概估算了。另外，可以自己计算一下算法中消耗内存较多的数据结构的体积。
有了观测数据和计算数据，就可以在算法中添加一些条件，来限制内存的使用了

如何合理使用内存呢？
首先，应该合理地选择数据结构，尽量高效地利用空间。
其次，应该合理地规划内存使用，把好钢用在刀刃上。
除了以上两点宽泛的原则，还有一个使用内存中的小技巧，或者说是一个注意事项。与C++的显示内存管理不同的是，CLR提供了一套完善的内存管理机制，程序中并不需要显示地进行内存的申请和释放，无效对象占用的内存会在适当的时机被自动回收。我们的竞赛平台中，在每一次调用选手算法的前后，会先调用CLR内存回收机制清理内存垃圾，再进行内存用量的计算。
为了使已经失效的对象占用的内存能成功地被释放，需要消除对其的引用。简单地说就是，如果你创建了一个对象，完成了任务之后想让它被回收掉，只要将所以指向这个对象的引用指向其它位置即可。参见以下两段代码示例：
object obj = new Object();
obj = null; // 此时，上一行创建的对象已经可以被回收

object obj = new Object();
obj = new Object(); // 此时，上一行创建的对象也可以被回收

策略篇
获得分数奖励，有三种方式。这三种得分方式楼上有介绍，下面主要分析如何设计算法，获得尽可能高的分数。

摆放面积越大的建筑越好么？
通常情况下，摆放面积越大的建筑能够立即得到的分数越高。但立即得分只是总分中的一部分。

建筑一定要放在同功能的地图区域上么？
建筑覆盖同功能的地图区域，可以获得额外的分数奖励。一般来说，有奖励的分数拿，何乐而不为呢

怎样获得比对手更高的分数，赢得比赛呢？
放面积尽可能大的建筑，覆盖尽可能多的同功能区域，这些基本的策略很容易被实现。所以，如果只做以上考虑，你的算法很难脱颖而出。一些额外的策略优化对于提升算法的分数是必须的。
一局比赛结束时，会根据算法覆盖的各类型区域的面积，进行一定的分数奖励。想方设法获得尽可能多的分数奖励，是提高算法得分，拉开与对手分数差距的一个有效途径。
对弈的游戏，拼的就是一个此消彼长，你死我活。所以，运用一些策略，使得在自己得分不受或少受影响的前提下，对手的得分受到较大影响，也是战胜对手的一个有效途径哦:smoke

技术篇
相信很多同学都是第一次接触.Net，下面介绍的一些.Net内置类型，可能会对算法的实现有帮助。

Array，即数组，如int[]。固定容量的线性存储结构。对其成员操作的时间复杂度是常数级。
List<T>，泛型的列表。可变容量的线性存储结构。与C++中的List不同的是，.Net中的List采用线性存储，对成员的访问是常数时间复杂度，并提供线性时间复杂度的插入和删除操作。其空间复杂度是O(N)。
Queue<T>，队列。.Net的队列是无优先级的简单队列，采用线性存储，提供线性空间复杂度及常数时间复杂度的入队和出队操作。
Dictionary<TKey, TValue>，字典，一种带索引的散列存储结构。这种结构的实现比较复杂，可以简单地认为它提供了亚线性时间复杂度的添加，查找操作，以及亚线性的空间复杂度。这是一个比较好的实现大量数据存储和查找的方案，但要注意key的选取，这个对性能的影响很显著。

好吧，今天暂时想到这些，先写到这里，大家如果有什么问题，欢迎回复提问。如果发现以上内容有什么错误或疏漏，也欢迎回帖指正。

L.. · L..

您好，我有以下疑问。

1：在BlockStatus中，BlockStatus.empty表示未放置任何建筑物，那么同时是否表示该区域不是Frozen（即不可放置建筑物区域）区域，还是说只表示该单元格仅仅未放置建筑物。

2：在Operation中,存在
public override bool Equals(object obj)
{
return this==(Operation)obj;
}
和
public override iint GetHashCode()
{
return base.GetHashCode();
}
这两个方法功能是什么，在什么情况下使用，个人不太明白（= =）。
谢谢。

songzh215 · songzh215

mark之

Iver · Iver

你好，L..：
１.Status和Type是两个无关的属性，它们各自有不同的意义。也就是说，状态为Empty的单元格，类型有可能是Frozen。
２.这两个方法与大家实现算法基本无关。因为Operation这个类型重写了==运算符，所以为了避免编译器警告，就重写了与之相关的几个方法。

wyj216 · wyj216

hello
IGameService中有这么个函数
      /// <summary>
      /// 通过调用本方法，获取一个与指定ID对应的建筑实例。
      /// </summary>
      /// <param name="id">
      /// 要获取的建筑的ID。
      /// </param>
      /// <returns>
      /// 与给定ID唯一对应的建筑实例，如果不存在，返回null。
      /// </returns>
      IConstruction GetConstructionByID(int id);
想问的是，如果一个ID好对应的建筑物本来是存在的，但是已经被使用了，那么这个函数返回的是null还是该建筑物啊~个人不太理解，而且想用相关性质

Iver · Iver

你好，wyj216：
无论建筑是否已经被使用，使用IGameService.GetConstructionByID这个方法都可以取得对应建筑的信息。

changkunpeng · changkunpeng

你好，请问一下，建筑物会不会有可能最外边的那列或几列全部是空白的呢？？

Iver · Iver

你好，changkunpeng：
有这种可能。

changkunpeng · changkunpeng

你好：
空间限制：算法执行过程中，内存占用不超过512MB；算法常驻内存的部分，不超过256MB；
这是.dll的内存占用（显示在dreamcity程序里的那个），还是整个程序的内存占用（资源管理器里的）？？

		自动登录	找回密码
密码			立即注册

开启梦想之门——竞赛题目解读

14 个回复

回复 3# L.. 的帖子

回复 6# wyj216 的帖子

回复 8# changkunpeng 的帖子

活字格认证