TOC
关于题目
BOP 的难度和 Code Hunt 根本不是一个难法。相比之下，Pex4Fun 和 Code Hunt 区更多地是以考验洞察力为主。
今天参加的 BOP2016 PRELIM A 共有两个 Sector 。很不幸的是，我最终只能成功提交一道题（00.04）。另有两道题则一直被 path bound exceeded 的错误困扰。
另请参阅：BOP2016 PRELIM A Leaderboard
00.01
输入为 `float[] a` ，输出为 `int[]`，包含了 a 中对应元素在整个 a 中的排名（从 0 开始），需要考虑并列排名的情况，有些类似于 Excel 的 `RANK` 函数。
思路：生成一个 [0, x.Length) 区间的整数序列 `ind`，然后使用 `Array.Sort(a, ind)` 进行排序。再开辟一个数组 `rank`，则此时 `ind[i]` 就意味着顺序排名第 `i` 的元素在排序前的原数组 `a` 中的位置。
本题较为麻烦的地方在于，如何处理并列排名的情况。我使用了双层循环。
以下是核心代码的残骸
// (r1,c1) and (r2,c2) are pairs of x-y coordinates
public static int[] Puzzle(double[] a)
{
var ind = Enumerable.Range(0, a.Length).ToArray();
Array.Sort(a, ind);
var rk = new int[a.Length];
var cur = 0;
for (int i = 0; i < a.Length; i++)
{
int j;
for (j = i + 1; j < a.Length && a[j] == a[i]; j++)
{ }
for (int k = i; k < j; k++)
{
rk[ind[k]] = cur;
}
cur += j - i;
i = j - 1;
}
return rk;
}
结果：path bound exceeded
后来使用 `Array.IndexOf` 代替内层第一个循环，问题依旧。
00.02
说实话，这道题，我并没有看出来什么规律。IQ捉急。
后来群里有人说，这是几何平均数。
好吧。
| a | Result |
|---|---|
| {1, 1, 1, 1, 1} | 1 |
| {1, 1, 1, 1} | 1 |
| {1, 1, 1} | 1 |
| {1, 1} | 1 |
| {1, 2} | 1 |
| {1} | 1 |
| {2, 1, 1, 1} | 1 |
| {2, 1} | 1 |
| {2, 2, 1} | 1 |
| {3, 1} | 1 |
| {5, 5, 1, 1, 1} | 1 |
| {2} | 2 |
| {3, 4, 5, 6} | 4 |
| {4} | 4 |
| {10, 5} | 7 |
| {10, 6} | 7 |
| {13, 4} | 7 |
| {4, 14, 7} | 7 |
| {5, 10} | 7 |
| {8, 7} | 7 |
00.03
这道题的输入比较复杂。此处列出其函数头
// (r1,c1) and (r2,c2) are pairs of x-y coordinates public static string Puzzle(int r1, int c1, int r2, int c2, string[] strs);
其中，`strs`指定了一个地图。地图中的 . 表示通路， # 表示障碍。需要求出从坐标 (r1, c1) 到达 (r2, c2) 的最短路径长度。如果没有可行通路，则返回 `”No path found!”`。
以下给出三个测试用例
CASE 1 (0,0) (2,6) 12 ".#....." ".#.#.#." "...#.#." CASE 2 (0,0) (0,2) 6 ".#." ".#." "..." CASE 3 ? <-- 因为 path bound exceeded 而无法显示参考结果 (0,0) (5,8) "........." "####.####" "...#.#..." ".#...#.#." ".#...#.#." ".#...#.#."
思路：当然是使用 BFS 啦~ 用队列解决一切问题。为了能把每一步的行、列和路程保存下来，最好做一个类或者结构体。
结果：path bound exceeded
由于代码过于惨不忍睹，此处就不贴上来了。
只知道最后为了试着解决这个问题，我甚至将 BFS 换成了 DFS + 距离启发 （<– 不知道是不是在瞎胡搞）。最后，比赛结束了……
00.04
输入一个 `int n`，按顺序输出所有可能的、包含 `n` 个左括号的、左右括号匹配的字符串列表。
思路：使用一棵树来表示每个字符的选择。由于每个字符只能选择`'(‘`、`’)’`之一，因此，最后会得到一棵二叉树。只要使用 DFS + 剪枝就可以了。分支截至字符串中的左括号数量等于 `n`，剪掉所有右括号数量大于左括号的节点。
代码如下
private class Node
{
public bool LP;
public Node Parent;
public int LPCount;
public int OpenLPs;
public int State = 0;
public Node L()
{
return new Node(true, LPCount + 1, OpenLPs + 1, this);
}
public Node R()
{
if (OpenLPs == 0) return null;
return new Node(false, LPCount, OpenLPs - 1, this);
}
public override string ToString()
{
var n = this;
var st = new Stack<char>();
while (n != null)
{
st.Push(n.LP ? '(' : ')');
n = n.Parent;
}
return string.Join(null, st);
}
public Node(bool lp, int lpCount, int openLPs, Node parent)
{
LP = lp;
Parent = parent;
LPCount = lpCount;
OpenLPs = openLPs;
}
}
public static string[] Puzzle(int n)
{
// the strings contain only parentheses
if (n <= 0) return new[] { "" };
if (n == 1) return new[] { "()" };
var list = new List<string>();
var root = new Node(true, 1, 1, null);
var st = new Stack<Node>();
st.Push(root);
// States
// 0 Nothing
// 1 L visited
// 2 R visited
while (st.Count > 0)
{
var nd = st.Peek();
if (nd.LPCount == n && nd.OpenLPs == 0)
{
list.Add(nd.ToString());
st.Pop();
continue;
}
switch (nd.State)
{
case 0:
nd.State = 1;
if (nd.LPCount < n)
{
var l = nd.L();
if (l != null) st.Push(l);
}
break;
case 1:
nd.State = 2;
var r = nd.R();
if (r != null) st.Push(r);
break;
case 2:
st.Pop();
break;
}
}
return list.ToArray();
}
结果：系统评级为1（It worked!），7分。这也是本场唯一拿到分的题目。
01.xx
很不幸，我没能活着从 TAIHU 出来。不知道 POYANG 如何（会不会像 PEX4FUN 的 Sector 03 一样）。
Epilogue
今年，大赛分为编程赛与创意赛，编程赛分初赛，复赛和决赛三部分。初赛和复赛在网络比赛平台上举行。今年初赛的网络平台为 Code Hunt平台。比赛时间为4月23日至4月24日，每天进行一场，时间为14:00-16:00。每场晋级1500人，共决出3000人晋级复赛。 [1]
按照今天 Code Hunt 的排名情况，似乎只要做出一道题，就能晋级了。不知道。总之，革命尚未成功，同志仍需努力。
今年的项目只有codehunt，各位oi/acm选手准备好被都是bug的平台玩奶子吧 [2]
我还是继续去 Coursera 上刷网课吧。在此之前……
我的工程优化好像还有4天的时间复习。
我的随机过程好像还有14天的时间复习。