版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [Atcoder ABC 184] (C - F)" categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• AtCoder
• 数学
• 概率
• 期望
• 搜索
• 记忆化搜索
• BFS
• 思维
• 构造
• 折半 date: 2021-02-02 12:05:57

比赛链接

C - Super Ryuma

Problem Statement

There is an infinite two-dimensional grid, and we have a piece called Super Ryuma at square $(r_1,c_1)$. (Ryu means dragon and Ma means horse.) In one move, the piece can go to one of the squares shown below:

More formally, when Super Ryuma is at square $(a,b)$, it can go to square $(c,d)$ such that at least one of the following holds:

• $a+b=c+d$
• $a-b=c-d$
• $|a-c|+|b-d|≤3$

Find the minimum number of moves needed for the piece to reach $(r_2,c_2)$ from $(r_1,c_1)$.

Constraints

• All values in input are integers.
• $1≤r_1,c_1,r_2,c_2≤10^9$

Input

Input is given from Standard Input in the following format:

$\begin{matrix} r_1&c_1\ r_2&c_2 \end{matrix}$

Output

Print the minimum number of moves needed for Super Ryuma to reach $(r_2,c_2)$ from $(r_1,c_1)$.

Sample Input 1

1 1
5 6

Sample Output 1

2

We need two moves - for example, $(1,1)\to(5,5)\to(5,6)$.

Sample Input 2

1 1
1 200001

Sample Output 2

2

We need two moves - for example, $(1,1)\to(100001,100001)\to(1,200001)$.

Sample Input 3

2 3
998244353 998244853

Sample Output 3

3

We need three moves - for example, $(2,3)\to(3,3)\to(-247,253)\to(998244353,998244853)$.

Sample Input 4

1 1
1 1

Sample Output 4

0

解题思路

做这题时我想到了国际象棋中的象, 如果两点同色, 则必然能在两步内到达

不难发现最多只需三步即可到达

其他的情况简单讨论下即可

代码参考

D - increment of coins

Problem Statement

We have a bag containing $A$ gold coins, $B$ silver coins, and $C$ bronze coins.

Until the bag contains $100$ coins of the same color, we will repeat the following operation:

Operation: Randomly take out one coin from the bag. (Every coin has an equal probability of being chosen.) Then, put back into the bag two coins of the same kind as the removed coin.

Find the expected value of the number of times the operation is done.

Constraints

• $0≤A,B,C≤99$
• $A+B+C≥1$

Input

Input is given from Standard Input in the following format:

$A\ B\ C$

Output

Print the expected value of the number of times the operation is done. Your output will be accepted if its absolute or relative error from the correct value is at most $10^{-6}$.

Sample Input 1

99 99 99

Sample Output 1

1.000000000

No matter what coin we take out in the first operation, the bag will contain $100$ coins of that kind.

Sample Input 2

98 99 99

Sample Output 2

1.331081081

We will do the second operation only if we take out a gold coin in the first operation. Thus, the expected number of operations is $2\times\frac{98}{98+99+99}+1\times\frac{99}{98+99+99}+1\times\frac{99}{98+99+99}=1.331081081...$

Sample Input 3

0 0 1

Sample Output 3

99.000000000

Each operation adds a bronze coin.

Sample Input 4

31 41 59

Sample Output 4

91.835008202

解题思路

比较简单的期望 MS

设 $f(a,b,c)$ 表示三种硬币各有 $a,b,c$ 个的时候, 胜利的期望步数

则

$$ f(a,b,c)=\frac{a\ f(a+1,b,c)+b\ f(a,b+1,c)+c\ f(a,b,c+1)}{a+b+c}+1 $$

代码参考

E - Third Avenue

Problem Statement

There is a town represented as a two-dimensional grid with $H$ horizontal rows and $W$ vertical columns.

A character $a{i,j}$ describes the square at the $i$-th row from the top and $j$-th column from the left. Here, $a{i,j}$ is one of the following: S, G, ., #, a, ..., and z.

# represents a square that cannot be entered, and a, ..., z represent squares with teleporters.

Takahashi is initially at the square represented as S. In each second, he will make one of the following moves:

• Go to a non-# square that is horizontally or vertically adjacent to his current position.
• Choose a square with the same character as that of his current position, and teleport to that square. He can only use this move when he is at a square represented as a, ..., or z.

Find the shortest time Takahashi needs to reach the square represented as G from the one represented as S. If the destination is unreachable, report -1 instead.

Constraints

• $1≤H,W≤2000$
• $a_{i,j}$ is S, G, ., #, or a lowercase English letter.
• There is exactly one square represented as S and one square represented as G.

Input

Input is given from Standard Input in the following format:

$\begin{matrix} H&W\ a{1,1}&...&a{1,W}\ \vdots\ a{H,1}&...&a{H,W} \end{matrix}$

Output

Print the shortest time Takahashi needs to reach the square represented as G from the one represented as S. If the destination is unreachable from the initial position, print -1 instead.

Sample Input 1

2 5
S.b.b
a.a.G

Sample Output 1

4

Let $(i,j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.

Initially, Takahashi is at $(1,1)$. One way to reach $(2,5)$ in four seconds is:

• go from $(1,1)$ to $(2,1)$
• teleport from $(2,1)$ to $(2,3)$, which is also an a square;
• go from $(2,3)$ to $(2,4)$;
• go from $(2,4)$ to $(2,5)$.

Sample Input 2

11 11
S##...#c...
...#d.#.#..
..........#
.#....#...#
#.....bc...
#.##......#
.......c..#
..#........
a..........
d..#...a...
.#........G

Sample Output 2

14

Sample Input 3

11 11
.#.#.e#a...
.b..##..#..
#....#.#..#
.#dd..#..#.
....#...#e.
c#.#a....#.
.....#..#.e
.#....#b.#.
.#...#..#..
......#c#G.
#..S...#...

Sample Output 3

-1

解题思路

简单的 BFS 会卡一个点, 要加优化

注意到任意一个传送门最多都只会经过一次, 所以我们可以把经过的传送门销毁

注意一下 std::list<>.erase() 的用法

代码参考

F - Programming Contest

Problem Statement

Takahashi will participate in a programming contest, which lasts for $T$ minutes and presents $N$ problems.

With his extrasensory perception, he already knows that it will take Ai minutes to solve the i-th problem.

He will choose zero or more problems to solve from the N problems so that it takes him no longer than $T$ minutes in total to solve them.

Find the longest possible time it takes him to solve his choice of problems.

Constraints

• All values in input are integers.
• $1≤N≤40$
• $1≤T≤109$
• $1≤A_i≤109$

Input

Input is given from Standard Input in the following format:

$\begin{matrix} N&T\ A_1&...&A_N \end{matrix}$

Output

Print the answer as an integer.

Sample Input 1

5 17
2 3 5 7 11

Sample Output 1

17

If he chooses the $1$-st, $2$-nd, $3$-rd, and $4$-th problems, it takes him $2+3+5+7=17$ minutes in total to solve them, which is the longest possible time not exceeding $T=17$ minutes.

Sample Input 2

6 100
1 2 7 5 8 10

Sample Output 2

33

It is optimal to solve all the problems.

Sample Input 3

6 100
101 102 103 104 105 106

Sample Output 3

0

He cannot solve any of the problems.

Sample Input 4

7 273599681
6706927 91566569 89131517 71069699 75200339 98298649 92857057

Sample Output 4

273555143

If he chooses the $2$-nd, $3$-rd, and $7$-th problems, it takes him $273555143$ minutes in total to solve them.

解题思路

直接查肯定 T, 折半搜索可以

将数据分成两部分, 一部分二进制枚举所有可能结果并排序; 另一部分二进制枚举, 二分查找前一部分结果中满足 "两部分结果之和 $<T$" 的最大结果

复杂度

$\displaystyle\Theta\left(n\cdot 2^\frac{n}{2}+2^\frac{n}{2}\left(\frac{n}{2}\right)^2\right)\implies O\left(\left(\frac{n}{2}\right)^22^\frac{n}{2}\right)$

代码参考