東京海上日動 プログラミングコンテスト2020のD - Knapsack Queries on a tree

 東京海上日動 プログラミングコンテスト2020のD - Knapsack Queries on a tree

　を通したのでメモ。

　PyPyでは公式解説の方法ではTLEを取ることが不可能なようだ。（他の人の提出を見たけど、通せている人はいなそうだった）

　半分全列挙をlogを使わずにやるテクニックを用いると、PyPyでも通るらしい。（多分全ての）PyPyの提出はこの方法で通している。

　……が、私が真似して書いてもなぜか通せなかった。

　ので、Kotlinで通そうと試みた。

　Kotlinだと、IntArrayなどを使って、最初から要素数を指定した配列で計算するのは速いが、mutableListOfとかで要素数を加えていこうとすると遅いようだ（良い方法があるのだろうか？）。

　なので、PyPyで速かった方法をそのままやろうとするとかえって遅くなる。

　そのため、公式解説の方法で、要素数を指定した配列のみを使ってやると通った。

　その言語での高速な書き方を理解していないと通せない問題は厳しい……。