ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Summer Festival Contest 2018 参加記録

Summer Festival Contest 2018 (Division 1) - AtCoder

結果は2完で7位でした。D問題の最速ACも取れちゃいました。

f:id:betrue12:20180826135558p:plain

DとEを振り返ります。

D - 木からパスへ (Tree--->path)

D - 木からパスへ (Tree--->path)

解法

問題の操作は、以下のように考えることができます。

  1. 与えられた木の辺を切断して、頂点を共有しないいくつかのパスに分解する。頂点は全てどこかのパスに含まれる。孤立した頂点(1頂点0辺の集合)もパスとみなす。
  2. 与えられたパス群を、パス数-1個の頂点を追加することで連結させる。

そのため、1. のパス分解において、なるべく少ない個数のパスに分解する方法を考えます。

何となく、長いパスで多くの頂点を巻き込んだほうが得なようにも見えますが、それは正しくありません。極端な例を挙げます。

f:id:betrue12:20180826141627p:plain

図のように、なるべく近いところでパスを作っていくほうが、他のパスを邪魔しなくてよいです。

このようにパスを作っていくため、与えられた木を根付き木として考えます。なるべく深いところ同士でパスを完結させてしまおう、という考えです。木DPのように深いところから見ていって、以下のようにパスを作っていきます。

f:id:betrue12:20180826143125p:plain

これを最深部から根まで行えば、全頂点を網羅するパスができているはずです。作られたパスの数-1が答えです。

ACコード

E - 石積み (Pyramid Piling)

E - 石積み (Pyramid Piling)

解法

この問題はまず「長さ  s n 次元三角数がどんな値になるか?」を把握する必要があります。2次元の  \frac{s(s+1)}{2} 、3次元の  \frac{s(s+1)(s+2)}{6} あたりが知識としてあると、  \frac{s(s+1)\cdots(s+n-1)}{n!} あたりになりそうだなあ…という予測は立ちますが、ちゃんと考えます。

問題文の定義より、「  x_{i} \ge 0 かつ  x_{1} + ... + x_{n} \lt s が成り立つ整数  (x_{1}, ..., x_{n}) の組」の数を考えます。これは「マルと仕切りを並べる順列」で考えることができます。

f:id:betrue12:20180826152122p:plain

上記の考え方により、条件を満たす整数の組は  _{n+s-1}C_{n} 通りです。これは先ほどの予測の式と一致しています。

三角数の一般式が得られたところで、問題を解いていきましょう。求めたい解は、

 \frac{s_{1}\cdots(s_{1}+N-1)}{N!} = \frac{s_{2}\cdots(s_{2}+N-2)}{(N-1)!}

を満たす  s_{1}, s_{2} であり、分母を払うと

 s_{1}\cdots(s_{1}+N-1) = s_{2}\cdots(s_{2}+N-2) \times N

となります。左辺は連続する整数  N-1 個の積、右辺は連続する整数  N-2 個の積  \times N です。要素数が同じなので、上手く対応付けられそうです。

  •  s_{1} = N
  •  s_{1} + 1 = s_{2}
  • ...
  •  s_{1} + N - 1 = s_{2} + N -2

を満たすように対応付けられれば良くて、これを満たすものは  s_{1} = N, s_{2} = N+1 となります。これは解として正当です。

 s_{1} = s_{2} = 1 も式を満たすのですが、問題で  s_{1} \ne s_{2} が要求されているのでこれはNGです。

ACコード

RubySubmission #3069695 - Summer Festival Contest 2018 (Division 1)

なお私の場合、すぐこの解にたどり着いたわけではなく、一度地道に探索するコードを書いて、その結果から規則性に気付いています。地道コードのほうもせっかくなので提出してリンクを貼っておきます。小さい入力値でしか動かないので当然ACにはならないのですが、このようなコードを一度書いて実行してみると気付きが得られるかもしれません。