ARC 103 E - Tr/ee (700)
解法
まず十分条件を列挙していく.
0-indexedとして,
- s[0] = 1
- s[N-1] = 1
- s[i] = s[N-1-i]
D問題でもそうだったが,自明な必要条件が必要十分条件になっているというパターン.
s = "100..01.." として,k番目に初めて1が現れるとする.
このとき,1つの辺を切断することで現れる高さ2の部分木は,k-1個の子をもつものしか作れないことがわかる.
これをどんどんやっていくと,
k-1番目までで x_1 = 1, x_2, x_3, .. (1<=a_i<=k-1) の子が作れるとして,
次に1がk番目に現れたとする. このとき,
k-1 = a_1 * x_1 + a_2 * x_2 + .. とx_iの線形和でノードがk個(子要素がk-1個)の木を作ってやることが必要になる.
一瞬DPをしたくなるが, よく見れば a_1 = k-1, a_2 = a_3 = .. = 0 としてやって
1の子要素で数を合わせれば良いことがわかる.
実際そうすれば解説動画のように必ずその木が作れることがわかり, 列挙した必要条件が必要十分条件であることもわかる.
メモ
閃きゲーかと思ったけど,実際に考察ができて見るとただの論理的帰着な気もする..
構築ゲーに関しては最小単位で数合わせ+2冪を考えてみるのがテンプレかな.
今回からけんちょんさんのブログの書き方(タグ付けとか)がわかりやすいので真似していくことにした.
