AtCoder Beginner Contest 156 Thank you for your hard work! Official page

The code I wrote this time is here The result was AC from A to D, and E was able to AC 5 minutes after the end of the contest. Frustrating: cry:

I will explain briefly below.

N and K are given as arguments,
The problem of adding `100 * (10-K)`

to N when K is 10 or less.

I think it was a 100-point problem.

The problem of outputting several digits when a certain number is in K notation. It's okay if you count the number of digits by turning around with a while statement.

```
while (n >= k) {
n = n / k;
digit++;
}
```

There are N people on the number line, and the point to minimize the sum of squares of the distance traveled by all of them and the problem of finding the sum of squares. First, select the coordinates that will be the center of N people (note that they must be integers). After that, I simply added the sum of squares.

Since it was `N <= 100`

, it seemed that I didn't have to worry too much about the amount of calculation.

Binomial coefficient problem. It uses the following properties:

```
2^n = {}_n C _0 + {}_n C _1 + {}_n C _2 +・ ・ ・\\
= \sum_{k=0}^n {}_n C _k\\
```

Then, what should be calculated is

```
2^n - {}_n C _0 - {}_n C _a - {}_n C _b
```

It will be.

I found the law 10 minutes before the end, so the implementation was not in time, Originally I was in N rooms one by one, and I noticed that once one move occurred, some room became 0.

I calculated the combination when K rooms have 0 people. Then

```
{}_n C _k \times {}_{n-1} C _{n-1-k}
```

It will be. Specifically, in the case of n = 6, k = 2,

```
{}_6 C _2 \times {}_5 C _3
```

is. So, take this sum

```
\sum_{i=0}^k \left( {}_n C _k \times {}_{n-1} C _{n-1-k} \right)
```

is. When k = 1 and when k is large, another consideration was required, but the basics can be calculated above. I calculated the inverse element first and wrote the amount of calculation well, but it was a little more.

It's untouched. I felt it was difficult because there were a lot of inputs, so I passed through. Lol

The rating is 944 → 974.

Overall it seems a little difficult. E The problem is a little more ... and I can't reach it. However, I was about to reach the E problem, so I got a sense of growth! Next time I want to do E problem AC ...!

Also, I wrote a mathematical formula using TeX. After all it is beautiful: chart_with_upwards_trend:

Recommended Posts