2014-2015 ACM-ICPC, Asia Tokyo Regional Contest

Problem A

Solved by zerol. 00:23 (+)

Problem B

Solved by zerol. 00:12 (+)

Problem C

Solved by ultmaster. 00:31 (+)

题意：从一条直线的一端走到另一端，有若干对关系 $(c_i, d_i)$ 表示 $c_i$ 必须在 $d_i$ 之后经过至少一次。求最小路程。

题解：一定是第一种情形。扫描线一下就好了。

图是从多校偷的。

Problem D

Solved by ultmaster. 01:57 (+)

题意：有若干柱子，要求打一个会反弹的炮，打到恰好 $d$ 米远的地方。至多反弹次数有限制。求最小速度。

题解：枚举至多反弹的次数。发射角度一定是 45 度以上占优，二分最小的可行角度。

Problem E

Solved by zerol. 03:09 (+)

题意：有一些互相垂直的街道，告诉你起始点和若干次经过一段路的方向，求可能的当前位置。如果刚好在转弯，那么方向可能是转弯前的也可能是转弯后的。

题解：分裂所有点，用 (x,y,d) 表示在 (x,y) 接下来要走 d，然后建图，要保证不能倒车。对于经过 dis 方向为 dir 有两种情况，分别是经过 dis-1 后方向为 dir 后再走一步或者经过 dis 方向为 dir。由于每次的 dis 很小，用 set 暴力一步一步走并去重然后检查合法性。

Problem F

Solved by zerol. 01:15 (+)

Problem G

Solved by kblack. 01:21 (+1)

题意：给一个合法的括号序列，每次翻转一个括号，要求再翻转一个括号使得序列仍旧合法，同时位置最左。

题解：( 翻 ) 很好做，寻找最左侧一个 ) 翻转即可，下面考虑 ) 翻 (。( 记为 +1，) 记为 -1，用线段树维护实时前缀和，我们只要找到最左侧的区间使得后侧全部 $\geq 2$ 的 ( 翻转即可。标记下放写错，演了自己。

Problem I

Upsolved by ultmaster & zerol.

题意：有若干巧克力按顺序出现，吃第 $i$ 块巧克力可以获得 $r_i$ 的能量和 $s_i$ 的收益。两个人轮流操作。每个人有两种选择：1. 吃掉；2. 花费 1 点的能量轮空，让对方操作。现在你和对方分别有 $a$ 和 $b$ 的能量，求最优情形下双方收益。

题解：显然，巧克力要么直接吃掉，要么在能量比对方多的时候花费 1 点的能量给对方吃掉。我们可以注意到，只有双方能量的差值才有意义，因为互相让来让去会消耗掉所有相等的部分；最后当一方的能量降为 0 时，还是花费了 1 点能量。

考虑这样一种记忆化搜索 $f(i,d)$ 表示在我已经累计了 $d$ 点能量差值（比对方多 $d$）时，面对还剩 $i$ 个的游戏局面，我能获得的最大收益。那么 $f(i,d) = \max \{$ 剩下的 $i$ 个物品的总价值 $- f(i-1, -t - r_i), f(i-1, t-1-r_i) \}$。边界条件是 $f(0,x)=0$。答案是 $f(n,a-b)$。

第二维可能的取值太多了，难以记忆化。但我们不难发现 $f(i,d)$ 在取值上的单调性，$d$ 越多，拿到的收益肯定越大，而这个变化的点不会太多。考虑自底向上，每一层，先求出我们关心的关键点，然后算出所有关键点的值，删除掉不必要的点。求值的时候就在下一层的 set 中二分查找。

没想到两个意识模糊的人还是在赛后把这道题过掉了。