diverta 2019 Programming Contest 2
Updated:
diverta 2019 Programming Contest 2
Source codes
Solutions
A - Ball Distribution
以下を出力する。
\[
\begin{align}
N - K & & & (K > 1), \\
0 & & & (K = 0).
\end{align}
\]
B - Picking Up
$0$-indexed とする。 $0 \leq i, j \leq N - 1$, $i \neq j$ に対し $\displaystyle \begin{pmatrix} x _ i - x _ j \\ y _ i - y _ j \end{pmatrix}$ の数が一番多いものを $\displaystyle \begin{pmatrix} p \\ q \end{pmatrix}$ にするのが一番コストが少なくて済む。そのコストは $N - cnt$ である。 $O(N^2)$ で求まる。
C - Successive Subtraction
解答
$0$-indexed とする。 $A _ i$ たちは昇順であると仮定して良い。このとき、 \[ \pm A _ 0 \pm A _ 1 \pm A _ 2 \pm \dots \pm A _ {N - 1} \] が候補の数字であるが( $\pm$ の組み合わせは任意)、このうち「全て $+$ 」と「全て $-$ 」はできない。操作の際に $x - y$ とすると、その後の $x, y$ の符号が同じになることはありえないからである。逆にそれ以外は全てできる(後述)。つまり答えは \[ -A _ 0 \pm A _ 1 \pm A _ 2 \pm \dots \pm A _ {N - 1} + A _ {N - 1} \] である。真ん中の $\pm$ は正になるように決めればよろしい。
その構成法： まず $now = A _ 0$ とする。次に $+$ の符号を選んだ $A _ i$ に対し $(now, A _ i)$ を出力し、 $now \gets now - A _ i$ とする。次に $now2 = A _ {N - 1}$ とする。次に $-$ の符号を選んだ $A _ i$ に対し $(now2, A _ i)$ を出力し、 $now2 \gets now2 - A _ i$ とする。最後に $(now2, now)$ を出力する。
ポイント
符号を先に決めうちするのがポイント。 これで実装の場合分けを避けることができ、楽になる。
D - Squirrel Merchant
前半：問題の分割
まずこの問題は $2$ つのパートに分けることができる。
- A で金属に両替して、 B でどんぐりに全て交換する
- B で金属に両替して、 A でどんぐりに全て交換する
これが可能であるのは、 B でどんぐりと金属の rate が一致しているため、たとえ間違えたとしても可逆であり、自由に交換ができるからである。中間地点ではどんぐりが多ければ多いほどいい。したがって 2 つの問題に分けることができる。
後半： DP
あとは DP で処理すればよろしい。
$DP[i] = i$ 個のどんぐりを最初に持っている時に、両替の末に持つことのできるどんぐりの個数の最大値
と定める。初期状態： $DP[0] = 0$, otherwise $DP[i] = 0$ 。答え： $DP[N]$ 。遷移： $i = 1, \dots, N$ に対し、 \[ DP[i] = \max(i, DP[i - g _ k] + g _ l, DP[i - s _ k] + s _ l, DP[i - b _ k] + b _ l). \] ここで index ははみ出さない場合のみ $\max$ をとるものと規約する。
ポイント
前半はわかったのだが、後半 $3$ 重ループは無理だなと思っていたら DP だった。いやはや。
E - Balanced Piles
前半： $D = 1$ の場合
DP によるのはほぼ明らかだろう。問題は状態をどのように管理するかである。まず現在の高さの最大値 $x$ は持っておかねばならない。次にその個数 $y$ も考察する必要がある。ここでポイントは 同じ高さに対しては操作する相対的な順番がすでに決まっているものと仮定する ことである。すると初期状態は $N!$ 個を分けて考察する必要があるが、最終状態が $N!$ 個の重複があるので、実は打ち消し合う。したがってこの仮定を入れて計算しても同じ結果が得られる。
以上の元で、状態の遷移の係数を考察する。単純に $(x, y)$ と書く。
- まず $(0, N)$ からスタートするが、ここから先への遷移は $(0, N) \to (1, 1)$ の $1$ 通りしかありえない。
- 次に $1 \leq x \leq H - 1$, $1 \leq y \leq N$ に対し、 $(x, y) \to (x + 1, 1)$ への遷移は、最小値のうち一番優先度の高いものを操作するので、 $1$ 通りしかない。
- 最後に $1 \leq x \leq H$, $1 \leq y \leq N - 1$ に対し、 $(x, y) \to (x, y + 1)$ への遷移は $(y + 1)$ 通りある。なぜなら最小値のうち一番優先度の高いものを操作し、最大値と同じ高さにするのであるが、そこで相対的な優先度の決め方が $(y + 1)$ 通りあるからである。
この結果、 3. の遷移を 2. に擬似的にまとめることが可能である。つまり \[ (0, N) \to (1, *) \to (2, *) \to \dots \to (H, 1) \to (H, N) \] であるが、最初の遷移が $1$ 通り、そのほかの遷移は $(1 + 2! + \dots + N!)$ 通り、最後の遷移は $N!$ 通りである。これで $O(H)$ で計算する道筋が整った。
後半： $D$ が一般の場合
$X = 1 + 2! + \dots + N!$ とする。すると $(x, *) \to (x + d, *)$ where $d \leq D$ に対して多重度 $X$ の辺が張られていると思えばよろしい。累積和を使って更新が可能である。
$DP[i] = (i, *)$ での場合の数、
$sum[i] = \sum _ {j < i} DP[i]$.
と定める。すると 1. は初期状態に落とし込むことができて、 $DP[i] = 1$ ($1 \leq i \leq D$), otherwise $DP[i] = 0$. 答え： $N! \times DP[H]$ ($(H, 1) \to (H, N)$ を考慮してある)。 遷移： $i = 2, \dots, H$ に対し、
\[
\begin{align}
sum[i] &= sum[i - 1] + DP[i - 1], \\
DP[i] &\mathbin{ {+} {=} } (sum[i] - sum[i - D])X.
\end{align}
\]
ここで index は $1$ 以上の際に有効であるとする。
ポイント
これは多重度を分けて考えないといけないので独力では正解に至れなかったのではないかと思う。
F - Diverta City
解答
$1$-indexed とする。再帰的に構成するものとする。 $n$ 個数の点からなる完全グラフ $G _ n$ であって、条件を充たすものを求めたとする。 $G _ n$ のハミルトンパスの最長値に $1$ を足した数を $M _ n$ とおく。
$V$ は正の数の集合であって、任意の $x, y \in V$ に対し $x + y$ と $x$ が相異なるものとする。具体的には前から貪欲に構成ができて $V = \{ 1, 2, 4, 7, 12, \dots \}$ のようになる。
このとき、 $G _ n$ に頂点 $n + 1$ を加えるのであるが、この時 $i$ と $n + 1$ の長さを $M _ n V[i]$ と定めると必ずうまくいく。その理由：まず $n + 1$ を通らないハミルトンパスの長さは $M _ n$ 未満な一方で $n + 1$ を通るハミルトンパスの長さは $M _ n$ 以上になるのでこれらが一致することはない。さらに $V$ に課せられた制約により、 $n + 1$ を通るハミルトンパスは $n + 1$ を通る辺を $1$ つかまたは $2$ つしか通らないのであるが、それらの長さの和は異なっている。また $n + 1$ を通るハミルトンパスで $n + 1$ を経由しない辺の長さの和は $M _ n$ 未満であるので、これらを加えてもやはり異なる値を取ることが保証される。
ポイント
これ昔に出た東大の学部入試に真ん中に $1$ を $99$ 個数並ばせる問題に発想がかなり近いと思う。
Others
しばらくレーティングは下がっていくけどまぁいいだろう。