# 某岛

… : "…アッカリ～ン . .. . " .. .
June 20, 2013

## Problem A. …..

### Brief description:

。。。转盘赌博问题。。一共有 37 个数字。。转到某个数字后得到这个投注的 36 倍。。。（负和？
。。现在你发现赌场的这个装置是有问题的。。既每次只会随机停留在投注最少的数字上。。

。。。问你此轮的最大的期望收益是多少。。）

### Analysis:

… 枚举 + 二分答案。。
https://gist.github.com/lychees

## Problem B. Rural Planning

### Brief description:

。。给定一个规模为 n 的点集，要求给出一个长度为 n 的排列。

( Small n = 10, Large n = 1000 )

### Analysis:

… Small 的话。。判断线段相交就可以。。（枚举所有排列。。暴力检测。。。
https://gist.github.com/lychees/5815413

。。之后考虑为什么满足条件的解一定存在。。
。。如图。。将凸包这样分成两半。。必有一部分的面积 >= 凸包面积的一半。

。。我们用大的去 “吸收” 小的。。所形成的图形的面积必定还会增加。。因此最后一定 > 凸包面积的一半。
。。考虑吸收过程。。最简单的方式。是将另外半个凸壳和折线全部放在一起排序。。。
。。需要注意的是。。求凸包的时候。。如果存在共线点。。需要全部算上。。
https://gist.github.com/lychees/5816430

## Problem D. Observation Wheel

### Brief description:

。。给定有 n 个槽位的一个旋转木马。。。游客到入口出时。。可能当前的槽位上面已经有人了。。需要等待一个空的槽位才能上去。。。
。。。为了缓和因等待而引起的不满情绪。。。等待的时间越久游客所支付的金币越少。。(初始为 N。。每多等待一回合。可以优惠 1￥。。。
。。。。。给定当前旋转木马的占据信息。。问装满人时。。公园所获收益的期望。。。
。为了简化问题。。。我们认为游客随机且一个一个进入。。既不考虑 “排队” 情况。。。并且假定游客上去以后就不会下来。。。
（ Small n = 20, Large n = 200 ）。。。

### Analysis:

##### Small dataset

In this problem we are interested in calculating the average amount of money we will make from filling up every gondola on our observation wheel. Because of linearity of expectation, this is equivalent to summing up the expected amount of money paid by each person. Given the fact that the amount a person pays doesn’t depend on the order in which gondolas got occupied, we can represent the current free/occupied state of gondolas as a bitmask and use dynamic programming to solve the small case.

Let E(mask) be the expected amount of money we make starting from the configuration represented by mask, where 0 represents an empty gondola, and 1 represents an occupied gondola. A person has a probability of 1/N of starting at any given position. Once that starting position is fixed, we simply find the first 0 following it (in cyclic order), and that’s where the person will eventually end up.

We’ll define f(i) as the index of the gondola occupied by a person who starts at position i. Similarly, let c(i) be the amount of money this person pays, as per the problem statement. Then we have the following recurrence: