典型90問まとめ 021～030 - 強くなりたい

022 - Cubic Cake（★2）

できる立方体のうち最も大きいモノを考えるとその一辺は $g = \gcd (a,b,c)$ 　である。

実際そうなるように分割したときの操作の回数が今回求めたい最小回数である。

各面に対して何回操作を行うかと考えることでその回数は

$\displaystyle \left(\frac{a}{g} -1\right)+\left(\frac{b}{g} -1 \right)+\left(\frac{c}{g} -1\right)$

と求まる。

$A$ を $B$ に合わせるのに必要な操作の最小回数は $S = \sum_{i=1}^n |A_i-B_i|$ である。

この $S$ が $S \leq K$ を満たしかつ $(S-K)\% 2 = 0$ であることがちょうど $K$ 回で $A$ を $B$ に合わせられるための必要十分条件。

木は二部グラフである！！！！

私はこれが思いつかなくて結局解説を見た。

隣り合う木に順に黒と白の色を塗っていってグループ分けする。すると同じ色に属する木は隣り合わないので黒と白のグループのうち大きい方を出力すれば良い。

set型を使うとin演算子が高速で動作する。これを使うと簡単。 AC

いもす法を使う。私はいもす法をあんまり使ったことがなかったのでちょっと実装に手間取った。

参考↓