https://atcoder.jp/contests/abc160

ABC160に参加したのでメモ。

A	B	C	D	E	F
o	o	o	o	o	x

A~Eは問題なく解けた。

D - Line++

頂点$i$と頂点$j$について、解説にあるように、迂回路を持つ頂点との位置関係で場合分けして計算した。別解として、BFSを使って２頂点間の最短距離を計算するという方法があったが、思いつきもしなかったことは反省すべき。BFSを使うことで、場合分けのケースを見落とすといったミスをすることがない。

E - Red and Green Apples

とりあえず、赤リンゴを美味さが大きいものから$X$個選び、同様にして緑色のリンゴも$Y$個選ぶ。こうして選んだ$X + Y$個のリンゴを美味しさについて昇順で並べて、無色のリンゴで置き換えたほうが美味しさの総和が増えるなら、置き換えるという操作を実装すればいい。

F - Distributing Integers

全方位木DPについては知らなかったが、木の再帰的な構造を利用して、DPで解くんだろうとはわかっていた。結局、組み合わせを数える(漸化式を立てる)ことができず解けなかった。あとで解く。