102. 今日解いた問題（2022.04.14）

本日より、問題を開いてから AC まで掛かったおおよその時間も記録しようと思います。

問題一覧

D - Harlequin (Diff: 1106)
E - Colorful Blocks (Diff: 1442)
E - Friendships (Diff: 1433)

自分の解法など

D - Harlequin

8分。

各色のりんごの残りを $b_i$ 個とします。任意の $i$ について $b_i = 0$ または $b_i = 1$ であるとき、 $b_i = 1$ であるりんごを全て食べれば勝てます。 $b_i \ge 2$ であるりんごがあるとき、この色のりんごは1ターンで食べきれないので、このターンでは勝てません。よって、相手の行動によって「必勝パターン」を作らせれば勝てます。

少し考察すると、「相手に偶数を押し付ければ必勝パターンに持ち込める」ことがわかります。奇数になっているりんごを食べて偶数にする、という行動を繰り返せば勝てます。よって、基本的に先手必勝です。ただし、最初のりんごが全て偶数だった場合のみ、先手が奇数を作らざるを得ないので後手が勝ちます。

以上より、「 $a_i = 1 \pmod 2$ である $i$ が存在するなら先手の勝ち、それ以外なら後手の勝ち」です。計算量は $O(N)$ 。

E - Colorful Blocks

15分。

まず、隣り合うブロックが全て異なる色で塗られているパターンを考えます。最初は $M$ 色で塗れて、その次は最初に選んだ色以外 $(M - 1)$ 色で塗れて、さらにその次は前に選んだ色以外 $(M - 1)$ 色で塗れて…となるので、 $M(M-1)^{N-1}$ 通りです。

次に、 $i$ 組同じ色で塗られているパターンを考えます。このような組は ${}_{N-1}C_i$ 通り考えられます。組にしたブロックを 1 つにして考えると、 $(N - i)$ 個のブロックを隣り合うものが異なる色になるように塗るパターン数を求める問題になります。以上より、 $({}_{N-1}C_i)M(M-1)^{N-i-1}$ 通りです。

出力する答えは $\displaystyle \sum_{i=0}^{K} ({}_{N-1}C_i)M(M-1)^{N-i-1}$ です。Combination の計算は、ループごとに分子・分母に数値を1つずつ掛けていくことで定数時間で行えます。計算量は $O(K)$ 。

E - Friendships

20分。

よく分からないので図を書いて考えてみます。 $N=4$ くらいで考えましょう。 $K=0$ のとき、完全グラフが条件を満たします。

f:id:ibako_piyo:20220414220446p:plain — $K=0$

ここから少しずつ辺を削って、 $K \ge 1$ のグラフを作れないか考えてみます。まず、現在隣り合っている頂点の組を列挙すると、

$(1, 2), (1, 3), (1,4)$
$(2,3),(2,4)$
$(3,4)$

です。

$K = 1$ の場合、 $(3, 4)$ の辺を消せばよいです。

f:id:ibako_piyo:20220414220631p:plain — $K = 1$

$K = 2$ ですが、 $(2, 4)$ を消せばよいです。…と考えると、最初に列挙した「完全グラフで隣り合う頂点の組」を逆に削っていけば $K$ の値を増やせることに気付きます。ただしグラフは連結であるという条件があるため、頂点 $1$ との組は削れません。そして、ここが $K$ の上限値です。