いろはちゃんコンテスト Day 1

I - リスのお仕事

Let us consider a graph whose vertices are (vertex ID, The cost used at last). If there exists a vertex having a lot of kinds of costs, it is difficult to update the distance efficiently. To perform efficiently, we prepare N special vertices (1,0),(2,0),...,(N,0) and connect (x,*) -> (x,0) with cost 1 and (x,0) -> (x,*) with cost 0. We can see that Dijkstra on this graph runs in O(N log^2 N), which is fast enough.

J - ヌクレオチド

When N is even, the inversion number is 2x(N/2-x) where x is the number of zeros in the first half. Look at two elements having different values. There are two cases. The first case is that 0 follows 1.

***0***1*** ***1***0***

In this case, the effect of two elements is exactly two. The second case is that 1 follows 0.

***1***0*** ***0***1***

Also in this case, the effect of two elements is exactly two. Thus, we can prove the first statement. We want to know the x such that 2x(N/2-x)=K. Since this is a quadratic equation, we can figure out the solutions by the quadratic formula. Once we get the x's, we just sum up C(N/2,x) for all x.

When N is odd, we can find out the answer similarly.

K - ルーレット

We do not have to compute the expectation but compute the sum of all possible patterns. It is not difficult to compute this.

L - をあ ぷろぶれむ

Fix the right end R, then the number of kinds of A[L] or ... or A[R] is at most 60. That is why, by or operation, the number of ones can increase at most 60 times. Let dp[R][X] be the number of intervals such that the right end is R and the bitwise OR of the elements is equal to X. We can compute this efficiently using std::map.