AtCoder Grand Contest 058

　Bまで二完。Bはここなどで既出だったらしい。

コンテストへのリンク

コンテスト後のツイート

C 「1と4」を「2と3」に繋ぐという方針が浮かんだが、その後の考察が進まず。
D、E　実験したが良い方針が出ず。DはA,Bを固定したら多項式になるっぽいのは分かった。

— titia (@titia_til) August 14, 2022

C - Planar Tree

　解説AC。

　「1と4」と「2と3」で分けて、「1と4」を「2と3」に繋げて消していき、全部消せたら（「2と3」のみ残ったら）OK、と考える方針は合っていたので、考え続けていれば解けた可能性はあるが、解法Stepを考えると1/4あたりまでしか辿り着けていなかったと思うので、ACまでは遠かったか。

　特に、同じ数字をつぶして良いということに気付いていなかったのが厳しい。

　まず、

・同じ数字をつぶす

・1と2が隣接→2だけ残す、3と4が隣接→3だけ残す

　として良いと気付くことが重要。

　そうすると、その後の操作では、

・...4 2 3...の4と3を結び、3だけ残す。（4 2を消す）

　というような操作しかなく、その操作で2と3のみが残れば良いので、2と4の個数、および、1と3の個数を比較すれば良いと分かる。