AtCoder Regular Contest 112のきろく - Flkanjin’s 競プロ録

グラフ問題考察が苦手です...

A - B = C (300点)
B - -- - B (400点)
C - DFS Game (500点)
D - Skate (600点): 未提出
E - Cigar Box (700点): 未提出
F - Die Siedler (900点、実行時間制限: 6 sec): 未提出
結果、感想

A - B = C (300点)

$A - B = C \Longleftrightarrow A = B + C$ であり、 $A = a + 2L,$ $B = b + L,$ $C = c + L$ としたとき $a = b + c$ $(-L \leq a \leq R - 2L,$ $0 \leq b,\,c \leq R - L)$ となる整数の組 $(a,\,b,\,c)$ を数え上げることと同値です。
$0 \leq b + c \leq 2R - L$ であるので、 $R - 2L \lt 0$ のときは条件を満たす組は存在しません。
$R - 2L \geq 0$ のときは $a = b + c = x$ となる $(b,\,c)$ の組を $x = 0$ から $R - 2L$ まで足し合わせればよく、各 $x$ について $(b,\,c) = (0,\,x),$ $\dots,$ $(y,\,x-y),$ $\dots,$ $(x,\,0)$ の $x + 1$ 組が存在するため $\displaystyle\sum_{x = 0}^{R - 2L} (x + 1) = \sum_{y = 1}^{R - 2L + 1} y = \frac{1}{2} (R-2L+1)(R-2L+2)$ が答えとなります。

B問題が分かってからまとめて提出しようと思ったらめっちゃ遅くなりました...

B - -- - B (400点)

$-1$ 倍する操作を反転操作、 $1$ 引く操作をマイナス操作と呼ぶことにします。反転操作は途中で行ってもあまり意味がないので最初と最後のみで行います*1。

反転操作を行わない場合

マイナス操作を $\displaystyle\left\lfloor \frac{C}{2} \right\rfloor$ 回まで行うことができるので $\displaystyle B - \left\lfloor \frac{C}{2} \right\rfloor$ から $B$ までの整数を作ることができます。

最初と最後に反転操作を行う場合

$C = 1$ の時はこの操作を行うことができません。
$C \geq 2$ のときはマイナス操作を $\displaystyle\left\lfloor \frac{C-2}{2} \right\rfloor$ 回まで行うことができるので $B$ から $\displaystyle B+\left\lfloor \frac{C-2}{2} \right\rfloor$ までの整数を作ることができます。
つまり、 $B$ から $\displaystyle B+ \max\left\{\left\lfloor \frac{C-2}{2} \right\rfloor,\,0 \right\}$ までの整数を作ることができます。

最初のみ反転操作を行う場合

マイナス操作を $\displaystyle\left\lfloor \frac{C-1}{2} \right\rfloor$ 回まで行うことができるので $\displaystyle -B - \left\lfloor \frac{C-1}{2} \right\rfloor$ から $-B$ までの整数を作ることができます。

最後のみ反転操作を行う場合

$C$ が奇数の時はマイナス操作を $\displaystyle\left\lfloor \frac{C}{2} \right\rfloor$ 回まで行うことができるので $-B$ から $\displaystyle -B + \left\lfloor \frac{C}{2} \right\rfloor$ までの整数を作ることができます。
$C$ が偶数の時はマイナス操作を $\displaystyle\left\lfloor \frac{C-2}{2} \right\rfloor$ 回まで行うことができるので $-B$ から $\displaystyle -B + \left\lfloor \frac{C-2}{2} \right\rfloor$ までの整数を作ることができます。

以上より $a = \displaystyle B - \left\lfloor \frac{C}{2} \right\rfloor,$ $b = \displaystyle B+ \max\left\{\left\lfloor \frac{C-2}{2} \right\rfloor,\,0 \right\},$ $c = \displaystyle -B - \left\lfloor \frac{C-1}{2} \right\rfloor,$ $d=\left\{ \begin{array}{ll} \displaystyle -B + \left\lfloor \frac{C}{2} \right\rfloor & (\text{$C$ は奇数})\\ \displaystyle -B + \left\lfloor \frac{C-2}{2} \right\rfloor & (\text{otherwise}) \end{array} \right.$ とすると、求める答えは $\# \{x \in \mathbb{Z} \mid x \in \left[a,\,b\right] \cup \left[c,\,d\right] \}$ より $(b - a + 1) + (d - c + 1) - \max\left\{\min\left\{b,\,d\right\} - \max\left\{a,\,c\right\}+1,\,0\right\}$ となります。

C - DFS Game (500点)

各頂点についてどの子を先に選ぶといいかで探索すればいいやと思ってDFSを書きましたが、先手後手が入れ替わる場合とそうでない場合があってWA。そこを修正しているうちに時間が来てしまいました。

頂点 $v$ を根とする部分木 $t_v$ でゲームを行ったとき、先手後手がそれぞれ何枚のコインを得ることができるか、という情報をもってDFSやDPを行います。ある木において先手が得るコインの枚数と後手が得るコインの枚数の合計はその木のサイズに一致するので、先手のコインと後手のコインの枚数の差のみを保持すればいいことが分かります。それを $d(v)$ とします。