AtCoder Beginner Contest 252

 　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

F 逆操作を考えると、小さい二つについてやると良いっぽい。（未証明）
G 経路数に帰着できそうだがグラフの構築に失敗。

— titia (@titia_til) May 21, 2022

G - Pre-Order

　解説を参考にAC。

　コンテスト中考えたことは次のような感じだった。

・「1 2 3 4 5 7 6」という列が与えられ、1から4までは順に一つ前の数が親になったとして、5の親が1になるとすると、（1の最初の子孫である2と3と4を無視して）「1 5 7 6」という配列について考えれば良い。

　これそのままだと（答えは一致するけれど）計算量が上手くいかない。この後、コンテスト中は迷走してしまったが、これを区間DPを用いて高速化しようと考えなくてはいけなかった。

　上では、「1から4までは順に一つ前の数が親になったとして」と、この部分も順に考えていたが、ここは「2 3 4」という配列を考えればOK、と気付くのが重要。

　すると、「1の子として2があるが、その次の子が5」だったとき、求める個数は「2 3 4」と「4 5 7 6」という列の個数の積になる。ここで、「5 7 6」でなく、「4 5 7 6」なのは、この後に出てくる7や6が1に繋がる可能性があるため。一番はじめの数字は何でもいいのだが、区間DPにするため、5の前の数字である4を便宜的に書いている。

　このようにすると、与えられた数列の区間の値により、大きい区間の値を求められると分かったので、区間DPができる。