5完3WA。いろいろやらかしてしまいました。
各問題
A - Horizon
与えられた式を計算するだけです。
B - Integer Division
与えられた式を計算するだけです2。
言語によって対応が変わりますが、c++なら負数のときは切り上げ除算的なことをする必要があります。具体的には(X - 9) / 10とします。
C - Knight Fork
親切にも図を用意してくれている通り、ある格子点から距離√5の格子点は8つしかないので、両方の点についてその8つの点の座標を求めて一致するものがあるかどうか全探索します。
D - Prime Sum Game
あらかじめ200までの数字が素数であるかどうかをエラトステネスのふるいなどを使って求めておきます。
すると全探索可能になります。
D問題のわりにはゆるすぎて提出を躊躇してしまいました...。
E - Subtree K-th Max
DFSで、帰りがけにDの値を積んでいくと、いい感じに部分木についてのDの値の配列が作れます。
一見計算量がたらなさそうに見えますが、Kが20以下なので都度20までに長さをカットしていけば大丈夫です。
各頂点について配列が作れさえすれば、クエリ一つにつきO(1)で、全体でO(Q)で答えることができます。
F - Construct Highway
制約より、木を作る問題であることがわかり、閉路ができてはいけないことがわかります。
しかし、構築方法は最後までわかりませんでした。
まとめ
EでK<=20の制約を見落として、無理と判断してFを先に考えて結局解けずにEに戻ったため結構なロスをしてしまいました。
まあEを考え続けていても水パフォあったかどうかは微妙なので、今日はダメでした。
