キーエンス プログラミング コンテスト 2020

Source codesPermalink

• My submissions (AtCoder)
• My source codes (GitHub)

SolutionsPermalink

A - PaintingPermalink

Flush $(N + X - 1) / X$, where $X = \max(H, W)$.

B - Robot ArmsPermalink

Set $I _ i = [X _ i - L _ i, X _ i + L _ i)$. Then, this problem is typical. We sort $\{ I _ i \}$ by the end of the interval and then the greedy algorithm works.

C - Subarray SumPermalink

Assume $0$-indexed.

SolutionPermalink

Let $d = S + 1$ if $S < 10 ^ 9$ and $d = 1$ if $S = 10 ^ 9$. Then we set $A _ i$ as follows to get $K$ sub-arrays whose sum is equal to $S$. $$A _ i = \begin{cases} S & i < K, \\ d & i \geq K. \end{cases}$$

Further questionPermalink

We cannot construct $\{ A _ i \}$ if $K > N$ since all $A _ i$ are positive.

D - Swap and FlipPermalink

Assume $0$-indexed.

ObservationPermalink

We use $V[i]$ to denote the $i$-th card. To simplify the manipulation, first we swap the red side and the blue side on each $V[1], V[3], \dots$. Then we see that our problem is equivalent to the following problem.

Suppose that we arrange the order of $V$. We adopt the number of the $i$-th card on the red side if $i$ is even and on the blue side otherwise. Are the cards in the ascending order?

Solution 1Permalink

We can separate two sequence, that is, the red sequence and the blue sequence. We try all the possibilities. First, we decide which cards are in the red sequence ($N - N / 2$ items). We sort the red sequence and the blue sequence separately and merge these sequences. If the final result is in the ascending order, this manipulation is doable. The number of the swaps is the inversion number which is easily calculated by BIT or Segment Tree.

We have to care for the same-number problem. To reach the minimum manipulation, we have to do tie breaks by the index of card if its value is same.

The time complexity will be $$O \left(2 ^ N N + \begin{pmatrix} N \\\ N / 2 \end{pmatrix} N \log N \right).$$

Solution 2Permalink

We can solve this problem by simple brute-force method in $O(N!)$-time. This solution can be converted into DP.

DefinitionPermalink

For $mask \in 2 ^ N$, for $0 \leq index < N$, we define as follows.

$DP[mask][index] =$ the minimum number of manipulation where we have already put the cards $V[i]$ in $i \in mask$ and we have used $V[index]$ last time, not having broken the ascending-order constraints.

AnswerPermalink

The answer is $$A = \min _ {i \in N} DP[2 ^ N - 1][i].$$ If $A = \infty$, flush -1.

Initial StatePermalink

Instead of presenting empty ‘last-used’ index, we adopt $N$. Therefore the initial state is $DP[0][N] = 0$; otherwise $\infty$.

TransitionPermalink

For all valid $(mask, i)$, We want to execute the following form. $$DP[mask’][j] \gets \min(DP[mask’][j], DP[mask][i] + d).$$ Here $j \not \in mask$, $mask’ = mask \cup \{ j \}$ and $d$ is the inversion number regarding $j$ and $mask$. This is executed if and only if $V[i] \leq V[j]$ holds in terms of either the red side or the blue side determined by their places.

In the normal DP, we use simple for-loops. But in this problem it does not work. Then, how can we visit all valid $(mask, i)$ in valid order? We can guarantee the validness by BFS. This is because $\lvert mask \rvert$’s ascending order must be one of the valid orders as long as the answer is not -1.

Also, be careful for the case $mask = \emptyset$ with $i = N$.

The time complexity will be $O \left(2 ^ N N^2 \right)$, which is a little slower than Solution 1.

E - BichromizationPermalink

F - MonochromizationPermalink

OthersPermalink