# physics0523's Hard Work #5 halc視点

まさかの全問未履修。$3$ 問目は解けなかったのだが…

$1$ 問目は特筆すべきところもないので略す。

# [Planar Tree](https://atcoder.jp/contests/agc058/tasks/agc058_c)

<details>
<summary>ネタバレ防止用</summary>
種類数の少ないところから考える。

$1,2$ の $2$ 種類の場合、$N=2$ なら問題ない。$3\leq N$ のとき、$1,2$ を結ぶ適当な頂点を結ぶと、その両側にできた領域は両方とも $2$ 種類であり、帰納法が回って可能なことがわかる。

$1,2,3$ の $3$ 種類の場合も、$N=3$ なら問題ない。$4\leq N$ のとき、$1,2$ を結ぶ適当な頂点を結ぶと、その両側にできた領域は両方とも $2$ 種類または $3$ 種類であり、やはり帰納法が回って可能なことがわかる。

ここから $4$ 種類にしたいが、$N=4$ のときに不可能なケースが紛れてやばい。何が起きているか観察すると、$1,2$ を結んだ時に $1,2,4$ のみからなる領域が完成してしまっていることがわかる。逆に、$4$ のみを含む領域を作らないようにすべての $1$ を何かしらの $2$ につなげることができれば可能であることがわかる。

$1$ と $2$ が隣接していれば結んで損がないことがわかり、$1$ どうし、$2$ どうしが隣接しているところはそれぞれ圧縮して問題がないこともわかる。

こうすると $1$ や $2$ の隣には $3$ か $4$ しか隣接しない状態が完成する。

$3$ や $4$ が隣り合っている部分を考えると、$3$ が $1$ つでも存在する区間は $3$ として、そうでない部分は $4$ として圧縮すればよいことがわかる。

このような文字列にしたときに、$1$ の数が $3$ の数より真に小さい必要があることがわかる。これが十分条件であることはやはり帰納法を回せば示される。$1$ と $2$ を結ぶもののうち、できた領域の一方が「 $3$ をちょうど $1$ つ含み、なおかつ $1$ を含まない」という条件を満たすようなものが存在することが示せるためである。

以上を良い感じに実装すればよい。適切に実装すれば $O(N)$ で判定できる。
</details>